screens) • Maps are generated, there are no key waypoints • Different kinds of landscape (mountains, lava, forests, …) • Hundreds of units that are active in the real-time • Fixed 60 ticks per second
0 astar 337336 B 2008 511908 B 3677 722690 B 3600 go-astar 43653 B 529 93122 B 1347 130731 B 1557 grid 996889 B 2976 551976 B 1900 740523 B 1759 paths 235168 B 7199 194768 B 6368 230416 B 7001
no heap allocations to build a path • Optimized for very big grid maps (thousands of cells) • Simple and zero-cost layers system • Works out of the box, no need to implement an interface
is in [0,255] range • 0 means that this cell can’t be traversed • Any other value specifies the traversal cost For the simplest cases, 0 and 1 are enough.
it without a pointer • Copying is trivial - a pair of 64-bit MOVQ instructions • No need to do a heap allocations • Requires no real memory fetching, unlike dynamic arrays
-> (coord, score) • Reset( ) - to re-use the memory Score is a Manhattan distance from coord to the destination. (*) The exact score calculation depends on the algorithm.
current possible moves to pqueue • Investigate all tempting routes first If some move brings us closer to the finish, we’ll check that route first. This is needed to reduce the average computation steps performed by the algorithm.
i < uint(len(q.buckets)) { e := q.buckets[i][len(q.buckets[i])-1] q.buckets[i] = q.buckets[i][:len(q.buckets[i])-1] if len(q.buckets[i]) == 0 { q.mask &^= 1 << i } return e } return T{} } TrailingZeros is basically a BSF+CMOV instructions on x86-64
- O(1) • Reset( ) - O(1)* Reset is constant to the number of buckets. Note that we’re using the mask to skip reslicing batches of buckets, so it’s quite fast.
12546 • The max size is 12546 * 8 => 100368 bytes (0,1 MB) After that, you can increase the Grid size for as much as you want; the CoordMap won’t get bigger.
element, but real memory clears will happen more often. Counters like uint32-uint64 make real memory clears almost impossible, but they will consume more memory per element.