Pathfinding - grid-aligned?

A possible solution is to not use the pathfinding solution as the movement solution. Instead, let units move around freely and perform precise object avoidance. The pathfinding solution could simply act as a goal path, such that the unit always tries to stay on the path but if it has to it can stray a little to avoid obstacles, and attempt to return to the path when done. So if a unit has to go through a narrow passage but the pathfinding path has it hitting a wall, then it can nudge itself off the path a little to squeeze through.

But that is my exact problem!

I'm sure the unit would find its own path in a narrow environment, if it wanted to go there so badly.
But this unit doesn't even want to go there, since it doesn't believe it is possible to go through the passage. This abstract, ideal path doesn't exist in the unit's mind!

I should somehow figure out that the path in fact exists, then my unit would follow it in whatever way it wants to. But I don't know how... yet.
I would have to know ahead if a unit can fit into a passage, without sending the unit first, so it could bounce around, checking it out itself.


I was thinking, maybe I could encode in each grid maximal circle that would fit there, having it's center somewhere inside the grid (not necessarily in grid's center) - this, as it seems quite expensive, would be done as preprocessing, and with updates for in-game created/destroyed static objects (like new buildings). Some similar calculations would have to be done for each grid-grid connection, telling who could go from one grid to another.

Only I don't know how to program this, at the moment... so I'm searching for other possibilities.

After computing your path using A*, why don't you do a "polishing" pass on your path?

Then, what you can do is move away your nodes from your unit's width from the nearest wall, if there should be a colision. So you'll need to change your movement to target 2D positions instead of grid nodes.

After that, what you could do in this polishing pass is remove the nodes that are not necessary, like if you have 3 nodes in a row, the one in the middle is useless.

For sure, you know its more complex than what I'm explaining (as you'll need to check for diagonals, not only corridors... and "bouncing" repositions, etc...), but it should get you on the good way of getting it working :)

Hope this helps

The 'duh' solution is to make your grid twice as dense, but to make sure that allowed/disallowed regions always start on an even cell and are even in extent (i.e. just like they are now, but with extra grid intersections in the middle of each current cell). That way you would hit the one in the middle of the gap and all would be well (and because of the 2×2 restriction, you always would). However, that would presumably slow your A* down by 4 times which might not be acceptable.

Quote:

Original post by xEricx After computing your path using A*

The thing is, I need to do this before computing the path from A*.

Let me rephrase:
While executing A star algorithm, when I'm examining a certain node, I need to check if my unit would fit there whithout collisions. This is where grid-aligned checkings seems to be doing bad job(*). A grid, and after that, a whole narrow passage is being rejected, and some other, longer path is being found, that doesn't use the passage.
And when A star is returning a path, I cannot repair it in any way, since it is wrong (meaning: all the way around the world) from the start.

(*) And this is where I need to act, but how?

Quote:

Original post by Bob Janova The 'duh' solution is to make your grid twice as dense, but to make sure that allowed/disallowed regions always start on an even cell and are even in extent (i.e. just like they are now, but with extra grid intersections in the middle of each current cell). That way you would hit the one in the middle of the gap and all would be well (and because of the 2×2 restriction, you always would). However, that would presumably slow your A* down by 4 times which might not be acceptable.

Thanks, but I figure my grid-map is already dense enough. I'm afraid that it is even too dense and I will need to shallow it a bit later.

I would say don't use a grid for pathfinding if you aren't going to restrict your units' movement to a grid.

Quote:

Original post by Mr Awesome I would say don't use a grid for pathfinding if you aren't going to restrict your units' movement to a grid.

So what other way of handling it are you suggesting?

Could you do a check while your creating the path? Since you're checking if the unit can fit through the passage already based on the grid, could you possibly refine the check to see if the unit could really fit through the passage? And then after you've found your path, impliment the fore mentioned idea of object avoidence to let the unit move through the passage the way it sees best (you already calculated that the unit can fit through so you know it will find a way).

Quote:

Original post by SirSmokey Could you do a check while your creating the path? Since you're checking if the unit can fit through the passage already based on the grid, could you possibly refine the check to see if the unit could really fit through the passage?

Yeah, I figure it could be something like that.
Only I don't know how that kind of check would look like. It's another thing to test for static collisions, and another to do full dynamic collision-tests for moving unit. With far A* path to generate, I would end up doing all-kind of collision tests of my unit with half of the world's objects.

Another thing - I think I don't need the exact knowledge if the passage is wide enough, only an estimate. If a unit of size 3.85 ends up not willing to go through 4.0 wide passage, so be it. But any worse-proportion cases would be eyes-hurting ;)

have u thought of changing choosing a path based on the actual square of a grid itself, to choosing a path based on the points that make up the grid itself?

for example:

instead of a path marked by X's like this:

-----
|x| |
-----
|x| |
-----
| |x|
-----

choose a path like this:
--x--
| | |
--x--
| | |
----x

either way you need to insure that there is an odd number of movement points between openings/objects, or make all of your AI agents a size = 1

could you bound your circle to a sqaure? Like in your example instead of testing with the circle make it a sqaure that has to move through the passage. That way you don't need to try and fit it through the center you just need to know that the passage is at least 4 sqaures wide. You could also change how you set the size of an object to the grid. If the object has a rdius of 1.5 the object you will create the test with will be a 3 x 3 square. If it's 3.1 you could say round it down so it will still be 3 x 3. Then if it reaches 3.5 or higher it will become 4 x 4 (or leave it to be 3 x 3 until it actually has a radius of 2 so you'll always be rounding down)This way you don't have to try and fit odd sizes around in a grid, but a square around in a grid.

Quote:

Original post by bosscheese either way you need to insure that there is an odd number of movement points between openings/objects, or make all of your AI agents a size = 1

I would work with my current method as well if I could afford that assumption.

Quote:

Original post by SirSmokey could you bound your circle to a sqaure? Like in your example instead of testing with the circle make it a sqaure that has to move through the passage. That way you don't need to try and fit it through the center you just need to know that the passage is at least 4 sqaures wide.

I'm planning on using human models instead of circles, so cylinders as colision shapes seem perfect, while box-simulated collisions could look awkward (don't know, maybe not so much, though).
But I don't see how this could resolve the situation, since boxes are not grid-aligned, and can move diagonally, and so on.

deffer right, I thought you already had the width check when computing your path.

If you're not planning to have an infinite amount of unit sizes, you could precompute for each "unit size" if they can or cannot use a node and store it as a flag in the node. This way you'll reduce your memory usage as it gets pretty costy if you have thousands of nodes.

What I would recommand though, is that you switch to a nav mesh. Using this mesh, its pretty easy to see a unit can pass through a node as the edges of each triangle or convex polygon represent the width of the entrance to this node.

Feel free to PM me if that's not clear enough

Instead of putting an object's center in a grid cell's center when testing, you need to try various alignments. For example, each square has 9 obvious alignment points (corners, edge centers, shape center). Circles (as far as A* pathfinding cares don't have such obvios alignment points besides the center, but you could arbitrarily select 8 additional points equally spaced around the circle (aligned such that they mimic the square's points, except the distance from the center is based on circle radius).

Once you have a set of alignment points C for the grid cell and a set O for the object, you can check for 'walkability' by testing each combination. Ex: Place the northern point of the object at the northern side of the cell and perform a test. If it passes, check validity, otherwise, try next combo (such as object north to cell northwest, etc). If all the tests fail, you know for sure the object can't possibly fit there.

If one of the tests passes, you need to make sure the object actually has enough room at that alignment. You can do this by finding which other grid cells are under the object at that alignment and making sure each of those is passable as well. Depending on how strict you want movement, you could consider any square with a single alignment point inside the circle must be unblocked, or you could require all of a square's alignment points to be inside the circle before it's considered. If you use 9 points, I would guess that requring 5 points to be inside the circle for it to block movement would be a good number. If all the cells covered by the object at this alignment are walkable, add this tile to the ones to consider.

You could probably get away with using only 5 points on the circle (N/S/E/W and center), but that would prevent it from moving very close to diagonal runs.

Quote:

Original post by xEricx If you're not planning to have an infinite amount of unit sizes, you could precompute for each "unit size" if they can or cannot use a node and store it as a flag in the node. This way you'll reduce your memory usage as it gets pretty costy if you have thousands of nodes.

Well, I'm planning to use only circular shapes, so I could just keep maximal radius of a circle that could fit into a certain grid. That was my original idea, only I don't know how to calculate this yet...

About the nav-mesh: I don't know what that's about, some more info, maybe?


Extrarius:
Doesn't your solution work the same as increasing the density of nodes?

Another possibility could be to not place your nodes on a grid, but instead in the 'middle' of open spaces. This way you would have many fewer nodes on the map, and could perform some relatively expensive tests on map loading to find the widest unit that could follow a particular edge and the most efficient route between two nodes (may not be a straight line if there is bad terrain in the way).

To place the nodes, you 'drop' potential nodes liberally across the map and have them 'roll' in an energy space defined by allowed terrain, i.e. the disallowed terrain repels them, and perhaps especially good terrain like roads could be slightly attractive. If two potential nodes collide, remove one of them. This way you end up with nodes in the local minima – low points – of the terrain's 'energy landscape'.

Then, to find a path, there are three steps:

1. Find the 'nearest' node to the start and end point by rolling down the energy landscape until you find one. It might be a good idea to try 'tipping' the landscape towards the other end of the path first, so the nearest node isn't in the wrong direction.
   
2. Perform normal pathfinding between those nodes.
   
3. "Pull tight" the path you make by shortening the curve until it touches bad terrain so it cannot be shortened any more, or is a straight line. This could well result in the path going through none of the original pathfinding nodes. I don't know how hard this step is.
   

I can see some potential problems with this approach, and without writing the entire thing myself couldn't tell you how hard they'd be to solve. You end up with a much simpler (and therefore faster) pathfinding step, but with extra processing to make the eventual path sensible.

If your only reason for using a grid is for pathfinding, then perhaps you should scrap the grid and use Points of Visibility.

I talk about POV in this post:
http://www.gamedev.net/community/forums/topic.asp?topic_id=370984&whichpage=1�

Just thought I'd mention it.

Yes, I think your 'POV' mesh is the same idea as I am using. The difficulty would seem to be ensuring you always get sufficient nodes, am I right?