This post describes the data structures used in the diagonal solver.
Coordinates – these will be used not just the cell center but also the edges.
• X, Y with a range of 2 * width + 1 and 2 * height + 1.
○ 16 x 16 => 33 x 33.
○ 32 x 32 => 65 x 65.
• The start cell is coordinate (1, 1).
• The start bottom left peg, which will be south west of the start cell is (0, 0).
• An Orthogonal cell has an odd coordinate for both the X and the Y coordinate.
• A diagonal/edge has an even coordinate for either the X or the Y coordinate.
• Coordinates are specified as (x, y).
○ x is the horizontal coordinate.
○ y is the vertical coordinate.
• Conversion between (x, y) and memory address is as follows:
Memory address = y * (2 * width + 1) + x.
ExpandQueue – used to track which cells we need to expand.
• This is a FIFO of a structure that has two elements – Coordinate and direction to expand.
○ The coordinate is the cell to expand next.
○ The direction is the direction to expand next from the cell.
• The size of the FIFO is (2 * width + 1) * (2 * height + 1).
○ It shouldn’t need to be this big.
○ The worst case scenario is to flood an empty maze because this will result in expansion of very cell and edge.
• If we implementing an A* algorithm based solver, this queue would be sorted with the coordinate expected to be on the lowest time path at the front of the FIFO.
For a 16 x 16 maze, where the coordinate and direction are two byte and one byte respectively, the FIFO will (2 * 16 + 1) * (2 * 16 + 1) * 3 = 3,267 bytes of RAM.
MoveCost Array – used to keep track of the path and cost of the path.
• This is an array that has two elements for each direction – the move that got us here and the cost to get here.
○ The reason entries are needed for each direction is that different paths could be passing through the cell in different direction.
• The path is an enumeration of moves. See “Diagonal Solver Introduction and Flooding” for types of moves.
• The cost is a 16 bit number.
○ To make it faster for the ARM architecture, it could be 32 bit if we have the RAM.
• The size of the array is (2 * width + 1) * (2 * height + 1) * 8 directions.
○ It shouldn’t need entries for the pegs but in the initial implementation, that won’t be optimized.
○ It should only need four directions because:
§ In the cell center, you can only be facing North, East, South and West.
§ In the edge, you can only be facing NorthEast, SouthEast, SouthWest, NorthWest.
However, for the first implementation, we are going to make this eight directions so that the direction from the ExpandQueue can be used directly. If this was only four directions, then when in the cell center, the direction would have to mean North, East, South and West and on an edge, the same four indices would have to mean NorthEast, SouthEast, SouthWest, NorthWest and we would need a comparison to determine this.
For a 16 x 16 maze, where the path is one byte and the cost is two bytes, the array will (2 * 16 + 1) * (2 * 16 + 1) * 8 * 3 = 26,136 bytes of RAM.
Incoming search terms:
- bouncingof diagonal wall c (1)