- Given a grid of the size width×height, with
0 0being the upper left corner in column row notation.
- The grid contains only open (passable) tiles and wall tiles (impassable).
- There are eight possible directions of movement: N NE E SE S SW W NW, where N means "up", and E "right".
- Moving diagonally is possible only when tiles of both related cardinal directions are passable.
For example, going NE requires both N and E neighboring tiles to be open.
- The result of the preprocessing phase is encoded as a set of passable tiles, each formatted as column row N NE E SE S SW W NW, where column row contain the tile coordinates, and the remaining numbers are distances in the corresponding directions.
2 0 3 -2 1 4 2 -1 -1 4means that for the tile of column 2 and row 0 going north there is a jump point 3 tiles away, going northeast there is a wall 2 tiles away, etc.
- The JPS+ runtime procedure should work as described in the section 14.7 of the cited publication.
- You need to implement the open list with a priority queue.
- The heuristic function in use for the A* part shall be the octile distance:
For two points
(x1,y1)and (x2,y2), the octile distance is given by dx + dy + (√2 - 2) . min(dx,dy)where dx = |x2-x1|and dy = |y2-y1|.
- For each node popped from the open list, your goal is to send one line, containing information about this node.
- Each line should be formatted as nodeColumn nodeRow parentColumn parentRow givenCost, where nodeColumn nodeRow contains the coordinates of the current node, parentColumn parentRow contain the coordinates of the node's parent, and givenCost is the cost of traversing from the start to the node.
- When the algorithm finds that path does not exist (open list is empty), you should send