Clyde学习笔记二（CoordIntMap）

CoordIntMap是一个基类为Map数据结构，是存储游戏地图场景数据的基础数据结构，在应用中一共涉及到3个类，第一个自然是CoordIntMap，另外还有Coord和Cell，Cell定义在CoordIntMap中，是一个内部类。

 

Coord用一个int来表示和存储一个2D的坐标，在存储和表示之前分别需要encode和decode。

    /**
     * Encodes the supplied coordinates (presumed to be in [-32768, +32767]) into a single
     * integer.
     */
    public static int encode (int x, int y)
    {
        return (x << 16) | (y & 0xFFFF);
    }

    /**
     * Extracts the x component from the specified encoded coordinate pair.
     */
    public static int decodeX (int pair)
    {
        return pair >> 16;
    }

    /**
     * Extracts the y component from the specified encoded coordinate pair.
     */
    public static int decodeY (int pair)
    {
        return (pair << 16) >> 16;
    }

 一个int类型有4个字节，前2个字节表示x坐标，后2个字节表示y坐标。取值范围从-32768一直到 +32767。

 

对于CoordIntMap，我们可以从它的定义中看到下面这2个接口，x、y是一个2D的坐标，显然CoordIntMap是一个以x、y2D坐标为key来存取对应的int值的这样一个map结构。

    /**
     * Retrieves the value at the specified coordinates.
     */
    public int get (int x, int y)
    {
       ...
    }

    /**
     * Sets the value at the specified coordinates.
     *
     * @return the previously stored value.
     */
    public int put (int x, int y, int value)
    {
        ....
    }

 但是它的内部存储是通过下面这个map来实现的

protected HashMap<Coord, Cell> _cells = new HashMap<Coord, Cell>();

 

 

可以看到，对外的接口与内部的存储方式并不一致，那么它是如何来转换这两者之间的差异的呢？

我们先来看一下CoordIntMap的构造函数：

    /**
     * Creates a new coord int map.
     *
     * @param granularity the size of the top-level cells, expressed as a power of two (e.g.,
     * 3 for a cell size of 8 by 8).
     * @param empty the value indicating the absence of an entry.
     */
    public CoordIntMap (int granularity, int empty)
    {
        _granularity = granularity;
        _empty = empty;
        initTransientFields();
    }

 

我们注意一下granularity这个参数，它的中文意思是粒度，在这里是2的幂指数，用来指定Cell的矩阵大小，granularity值越大，Cell内包含的元素越多，粒度越小。

Cell的构造函数：

        /**
         * Creates a new cell.
         */
        public Cell ()
        {
            _values = new int[1 << _granularity << _granularity];
            Arrays.fill(_values, _empty);
        }

 1 << _granularity << _granularity这个表达式的数学含义是4的_granularity次方。默认_granularity=3，初始化一个8x8的数组，并且初始化成空值。

 

Cell内部是用一个一维数组来表示和存储数据的，也就是说最终的数据都是存储在下面这个数组内的。

        /** The values in the cell. */
        protected int[] _values;

 

那么，CoordIntMap是如何通过x、y这组2D坐标映射到_values数组中的值呢？我们来看一下get方法的具体实现：

 

    /**
     * Retrieves the value at the specified coordinates.
     */
    public int get (int x, int y)
    {
        Cell cell = getCell(x, y);
        return (cell == null) ? _empty : cell.get(x & _mask, y & _mask);
    }

    /**
     * Returns the cell corresponding to the specified coordinates.
     */
    protected Cell getCell (int x, int y)
    {
        _coord.set(x >> _granularity, y >> _granularity);
        return _cells.get(_coord);
    }

 

 

首先，x、y被映射成一个Coord，然后根据这个Coord的值在内部map中找到cell，最后再从cell中得到值。这里最重要的就是对x、y的映射算法，这也是整个数据结构的核心。

 

x >> _granularity, y >> _granularity翻译成数学语言是x除以2的_granularity次方，y除以2的_granularity次方。还记得前面提到过的对Cell构造函数的解释吗？每一个Cell都是一个2的_granularity次方 x(乘) 2的_granularity次方的结构，那么这里对x、y的映射是用来计算x、y所对应的value所在的Cell的坐标。

 

在得到Cell后如何再取得最终的值呢？在理解cell.get(x & _mask, y & _mask)这个表达式之前我们先来看下CoordIntMap构造函数中的调用的initTransientFields()这个方法。

 

    /**
     * Initializes the transient fields.
     */
    protected void initTransientFields ()
    {
        _mask = (1 << _granularity) - 1;
    }

 这个方法用来计算mask的值，我们刚才已经看到，这个mask在我们从Cell中取值会被用到。那么，在这里的这个表达式(1 << _granularity) - 1 我们已经比较熟悉了，数学含义就是2的_granularity次方-1。如果：

 

_granularity = 2， 那么1 << _granularity) - 1 = 3， 2进制值为 11
_granularity = 3， 那么1 << _granularity) - 1 = 7， 2进制值为 111
...

 

我们回过头再来看表达式cell.get(x & _mask, y & _mask)，分别用mask对x、y做和的位运算，其数学含义等同于分别用2的_granularity次方除x、y取余，这样其实得到了x、y映射到Cell中的坐标。

 

为了更好的理解，特意编辑了2个实例示意图，相信大家都能理解。

 

 

既然CoordIntMap它是一个Map，那么它必然要提供一个接口供调用者来遍历每一个entry。CoordIntMap对外提供了这样的一个方法，它用一个Iterator来遍历内部的数据。

 

    /**
     * Returns a set view of the map entries.
     */
    public Set<CoordIntEntry> coordIntEntrySet ()
    {
        return new AbstractSet<CoordIntEntry>() {
            public Iterator<CoordIntEntry> iterator () {
                return new Iterator<CoordIntEntry>() {
                	...
                };
            }
            public int size () {
                return _size;
            }
        };
    }

 

Iterator的定义：

 

public Iterator<CoordIntEntry> iterator () {
    return new Iterator<CoordIntEntry>() {
				...
        public CoordIntEntry next () {
            checkConcurrentModification();
            if (_centry == null) {
                _centry = _cit.next();
            }
            while (true) {
                int[] values = _centry.getValue().getValues();
                for (; _idx < values.length; _idx++) {
                    int value = values[_idx];
                    if (value != _empty) {
                        Coord coord = _centry.getKey();
                        _dummy.getKey().set(
                            (coord.x << _granularity) | (_idx & _mask),
                            (coord.y << _granularity) | (_idx >> _granularity));
                        _dummy._values = values;
                        _dummy._idx = _idx;
                        _idx++;
                        _count++;
                        return _dummy;
                    }
                }
                _centry = _cit.next();
                _idx = 0;
            }
        }
				...
        protected Iterator<Entry<Coord, Cell>> _cit = _cells.entrySet().iterator();
        protected Entry<Coord, Cell> _centry;
        protected int _idx;
        protected int _count;
        protected int _omodcount = _modcount;
        protected CoordIntEntry _dummy = new CoordIntEntry();
    };

 

 这里只截取了next方法，展示了跟前相反的操作过程，即通过内部的存储数据来取得最初的x、y的值。这里最关键的两个表达式：

(coord.x << _granularity) | (_idx & _mask)

(coord.y << _granularity) | (_idx >> _granularity)

这两个表达式分别取得x、y的值然后存储为dummy中的key，这里的key虽然也是Coord类型，但含义跟我们前边看到的那个Coord完全不同，存储的直接是x、y的值

 

        /** The coordinate key. */
        protected Coord _key = new Coord();

 

 如果我们跑一下下面的这段代码

 

		CoordIntMap map = new CoordIntMap();
		map.put(5, 7, 112);
		map.put(1, 3, 57);
		map.put(8, 6, 33);
		Set<CoordIntEntry> set = map.coordIntEntrySet();
		for (CoordIntEntry entry : set) {
			System.out.println("key: " + entry.getKey());
			System.out.println("value: " + entry.getValue());
		}

 可以预期得到的输出为key: [1, 3]

 

value: 57
key: [5, 7]
value: 112
key: [8, 6]
value: 33

 

备注：本文中涉及到的位运算及其含义

1 << _granularity << _granularity

4的_granularity次方

 

x >> _granularity, y >> _granularity

x除以2的_granularity次方，y除以2的_granularity次方

 

 

(1 << _granularity) - 1

2的_granularity次方-1

 

 

x & _mask, y & _mask

2的_granularity次方除x、y取余

 

(coord.x << _granularity) | (_idx & _mask)

coord.x乘以2的_granularity次方加上_idx除以_mask取余

 

(coord.y << _granularity) | (_idx >> _granularity)

coord.y乘以2的_granularity次方加上_idx除以2的_granularity次方取整

 

 

后记：

CoordIntMap的实现中大量使用了位运算，这样做的目的主要是为了提高效率，毕竟这是一个基础性的数据结构，特别是在处理地图场景等大数据量的时候，效率还是比较关键的。其实类似的用法我们在JDK中也能看到，比如在HashMap中，通过hashcode定位数组index的取余方法JDK中是这样实现的：

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 

在这里，当length为2的幂时，h & (length-1)等价于h % length，但是前者的效率要高于后者。怎么样，这里的length - 1和CoordIntMap中的mask是否有异曲同工之妙呢？