A* pathfind - shortcuts in gridbased-paths?

Started by
27 comments, last by IADaveMark 6 years, 8 months ago

Could I not just compare the travel cost between: 

1. node p and p[i+2] (stepping along all 3 nodes)
2. node p and p[i+2] (stepping along a straight line from the two outmost nodes)

both using the calculation method for continuos movement?

Advertisement

If you look at your initial graphic you'll see that it's not as simple as that. You would have to be able to compare a grid-based path of N nodes against a straight line route of 1..N nodes, where you have to perform several calculations on the straight line route to see how much time it spends within each grid square. It's not impossible but it is quite awkward. And it no longer guarantees that the final route is the shortest, because you've added a large number of alternatives - i.e. different 'string pulling' choices - which you're not comparing against each other.

Ah I see... Yes seems complicated.

But what is the normal way to do this? I mean games like banished has ( I assume since the game is grid based) grid-based pathfinding in the bottom, but units can "cut" diagonally over open fields ("continous movement", not zigzagging over perfect tile-centers). And it has terrain cost (road tiles are quicker and units prefer those).

You might be able to fudge it and pretend it's a grid based path.  You might get funny results now and then, but it might do a good enough job at avoiding horribly slow tiles and staying on fast tiles.  Would require testing.

Otherwise, you probably have to do something like what Kylotan said, get the tiles under the line, find how much of the line is under each tile, do a cost * length calculation for each tile.  Hopefully your units aren't super thick, or it becomes more like casting a rectangle / capsule and doing tiles under that, which gets uglier.  If you're a city builder and it's tiny little people, you can probably get away with a single ray.

 

Yes my units are single-point entities :)

That's good, I've mucked with units that are rectangular and have a turn radius.  It gets expensive very fast.

Maybe your grid-based path calculation is the wrong approach? What if you convert the grid to navmesh, and then do continuous path computation?

Unfortunately, the above sentence is as far as my knowledge goes, I have no idea of implications if you take that approach.

 

I agree that grid-based is the root of the problem here. I just assumed that he couldn't switch to navmesh for whatever reason.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

This topic is closed to new replies.

Advertisement