A Star pathfinding on oblique map

Question

I'm making an RPG and want to make npc ai to navigate the city. I am using polylines for collision detection, and my map is 2D, but oblique styled. I am considering using the A* algorithm to help them navigate.

I've gotten the A* algorithm to work with a top-down 2D array of nodes:

But am not sure how to go about implementing this in my game.

The overall world is 100x100 64x64px tiles, but the viewport (red box) only shows a small portion of them:

My questions are as follows:

• Do I make a 2D 100x100 array, each cell size 64x64 px to mimic the real map?
• How do I account for the polyline barriers/collision if 1's (unwalkable) and 0's (walkable) can only be assigned to a square cell?
• Performance: is it better to just created a pathing grid for the viewport, or always generate one for the entire 100x100 map?
• Barriers/Collision: I create my collision barriers directly in Tiled. Is there a way to programmatically insert unwalkable into the matrix for a given location of the barrier?

I am lost as to where to go next in translating this to my game.

Thanks!

Answer 1

For the A-star algorithm you must provide a data structure that, for vey legal current position of the agent, provides the set of possible moves from that location along with the cost of making that location change.

The most common means of providing such a data structure, especially for a rectangular grid, is a 2D array of lists.

However for more complex graphs, such as road networks, a more complex data structure might be required.

The visual representation of your map is (or at least should be) completely separate from, and irrelevant to, the data structure presented to A-star.

For your example a 2D array (or list of lists) of nodes, each node having a list of the cost to move in each orthogonal and diagonal direction would be sufficient. You could for example choose to have the list of possible moves for each node be an ordered list of the legal moves, starting at North and stepping CW 45 degrees each time to NE, E, SE, S, SW, W, NW. A common choice in this case would be to use either a cost of 0 or -1 represent an illegal move, as no actual cost would ever be one of those values on a graph with an admissible heuristic.