# Correct way to handle path-finding collision matrix

Here is an example of me utilizing path finding. The red grid represents the grid utilized by my A* library to locate a distance. This picture is only an example, currently it is all calculated on the 1x1 pixel level (pretty darn laggy).

I want to make it so that the farther I click, the less accurate it will be (split the map into larger grid pieces). Edit: as mentioned by Eric, this is not a required game mechanic. I am perfectly fine with any method that allows me to make this accurate while still fast. This isn't the really the topic of this question though. The problem I have is, my current library uses a two dimensional grid of integers. The higher the number in a cell, the more resistance for that grid tile. Currently I'm setting all unwalkable spots to Integer Max.

Here is an example of what I want:

I'm just not sure how I should set up the arrays of integers of the grid. Every time an element is added/removed to/from the game, it's collision details are updated in the table.

Here is a picture of what the map looks like on my collision layer:

I probably shouldn't be creating new arrays every time I have to do a path find because my game needs to support tons of PF at the same time.

Should I have multiple arrays that are all updated when the dynamic elements are updated (a building is built/a building is destroyed).

The problem I see with this is that it will probably make the creation and destruction of buildings a little more laggy than I would want because it would be setting the collision grid for each built in accuracy level. I would also have to add more/remove some arrays if I ever in the future changed the map size.

Should I generate the new array based on an accuracy value every time I need to PF?

The problem I see with this is that it will probably make any form of PF just as laggy because it will have to search through a MapWidth x MapHeight number of cells to shrink it all down.

Or is there a better way? I'm certainly not the best at optimizing really anything. I've just started dealing with XNA so I'm not used to having optimization code really doing much of an affect until now... :(

EDIT:

While this doesn't directly relate to the question, I figure the more information I provide, the better. To keep your units from moving as accurately to the players desired position, I've decided that once the unit PFs over to the less accurate grid piece, it will then PF on a more accurate level to the exact position requested.

• I would go with a fixed size grid that's a lot less fine than both images you've shown. Give each cell 3 states. Full/Partially/Not occupied. A* must ignore full, and partially occupied cells should get a penalty. Then do your normal movement. When 2 objects are both in a partially occupied cell subdivide that cell temporarily to find a path for both. (this is a comment because these small ideas don't do justice to the large amount of info you've put in your question. +1 for that!) – Roy T. May 26 '12 at 13:16
• "I want to make it so that the farther I click, the less accurate it will be (split the map into larger grid pieces)." Is this a gameplay requirement, or merely a concession you're willing to make in the name of optimization? – Eric May 30 '12 at 10:38
• @Eric I figure that it will be impossible to make the process of PF fast, non-CPU intensive, and accurate (as is my understanding with the whole, three sided triangle, pick only two). Anyways, if I could get it accurate while still being fast and not needing high system specs, I would love to utilize it. Thanks for the comment though. I guess that is true. I'll add an edit. +1 for you. – Freesnöw May 30 '12 at 19:52

Not sure if I properly understand your question, but I will take a stab at it. I would try using a quadtree (similar to a sparse voxel octree, but just 2D). You could represent the entire world as 4 quadrants, and then split each quadrant recursively where you want to achieve higher accuracy. See http://en.wikipedia.org/wiki/Quadtree

Edit: to elaborate...

I would build a quadtree with each node valued between 0.0 and 1.0. To build a node, add up all collidable units inside it, and divide by total number of units. So, if a given quadrant had 16 collidable units, and 48 empty units, its value would be 0.25. If a given quadrant is 1.0 or 0.0, you don't need to build children nodes for it (completely empty or full). You could then select paths by recursively drilling down. Have a start quadrant, and and end quadtrant, then build a path between them by probabilistically selecting nodes that are the least full.

• I've read about this, however, it doesn't really have anything to do with my question. My question is how to implement something like this into my system. I need to know how I should handle the changing of my arrays to represent the accuracy needed. – Freesnöw May 30 '12 at 19:58
• @XanderLamkins - I am aware that you want to use multiple arrays, but I am trying to suggest a better solution. Managing multiple arrays probably is not going to help you in terms of speed and memory usage. Here is how I would implement it: Use a quadtree where each node has a value between 0.0 and 1.0 (representing how full of collidable objects the quadrant is). That way you can plot out paths recursively selecting sections that are the least "full". To build the quadtree, its just like a mip map: add up all the collidable units and divide by the total number of units. – Gavan Woolery May 30 '12 at 22:56
• Fair enough, just trying to point you in (what I thought would be) a good direction. I was not expecting this to be a candidate for best answer, just providing some info - always happy to elaborate if need be, but generally I don't have much time to write more than short answers. :/ – Gavan Woolery May 30 '12 at 23:35
• Well, it is some good information non the less. Don't worry, I've already +1'd you for that :) – Freesnöw May 31 '12 at 0:19

You can make the grid size of each array twice as big as the last one, and let each tile in the lower-resolution grids equal to the maximum value of the smaller tiles it covers, see the figure below.

That way they would be very easy and fast to update. For each lower-res array you get the wanted indices by simply dividing by 2. When a tile's value is changed it will be pretty straight forward to update all the arrays.

If a tile's value is increased, set the value of all the covering tiles to max(newValue,currentValue).

When a tile's value is decreased, refresh the covering tiles to make sure they have the correct value. You can be clever about this and compare the previous value with the new one and only update if neccessary, or just check all the tiles in the most detailed array and use the highest. This update is really fast anyways since you aren't rebuilding the whole array but just updating the affected tiles, so it shouldn't matter much for performance.

If you use this method, you will have to be careful not to make any passages narrower than double the dimension of the tiles in the lowest-resolution array, or the PF might not find the optimal path.