プログラミング アルゴリズム 座標(x, y)を一意の値に変換してハッシュテーブルで管理する


タグ: 

This topic contains 0件の返信, has 1件の返信, and was last updated by  ろかん Lv.26 3 年 1 ヶ月.

  • 概要

    ゲームである特定の座標の情報を保持する場合の方法はいくつかあります(二次元配列とか…)。

    今回はハッシュテーブルを用いた効率のよい座標管理方法を説明します。
    —-
    ちなみにハッシュテーブルを利用するには下記を用います。
     ・Rubyだと組み込みライブラリのHashクラス
     ・C#(.NET)だとSystem.Collections.Generic名前空間のDictionaryクラス
     ・JavaだとHashMapクラス
    などなど…
    —-

    方法

    ハッシュでの座標管理では、座標をキーにします。

    座標をキーにすると聞いて、ぱっと思いつくのは次のような方法(Rubyの場合)

    # 指定座標の情報更新
    def set_position_value(x, y, value)
      @potition_hash ||= {}
      @potition_hash[[x, y]] = value
    end
    # 指定座標の情報取得
    def get_position_value(x, y)
      @potition_hash ||= {}
      @potition_hash[[x, y]]
    end

    X座標とY座標の配列をキーに、その座標の情報(value)を管理しています。
    これはこれで間違いでは無ないですが、(少なくともRubyの場合は)配列をキーにするのはちょっと非効率(重い)です。

    ではどうするか

    シフト演算論理和を使って、X座標とY座標という2つの値を一意な1つの値に変換したものをキーとして利用します。
    どのように変換するかというと次のような感じ(Rubyの場合)

    # 座標の変換
    def point(x, y)
      y << 9 | x
    end

    9 という数字はどれだけ左にシフトさせるかを表しています。
    管理する座標の範囲によって調整してください。
    座標の範囲に対してこの値が小さすぎると、変換後の値が一意にならない(異なる座標同士で重複が発生してしまう)可能性がでてきます。

    尚、RPGツクールVXのマップの座標管理をする場合は、例のように 9 シフトさせれば問題なく動作します。
    (マップサイズの上限が500*500なので 8 だと足りない)

    結果

    最終形はこんな感じになります(Rubyの場合)

    # 指定座標の情報更新
    def set_position_value(x, y, value)
      @potition_hash ||= {}
      @potition_hash[point(x, y)] = value
    end
    # 指定座標の情報取得
    def get_position_value(x, y)
      @potition_hash ||= {}
      @potition_hash[point(x, y)]
    end
    # 座標の変換
    def point(x, y)
      y << 9 | x
    end

このナレッジに返信するにはログインしてください。