Path finding without a grid

[jacquesr]

Hi,

I am currently researching path finding. I am aware of the a-star algorithm and I have implemented it myself years ago. While it's perfectly suited for gridded system, I want to know if there are also algorithms that can do path finding without a grid, e. g. by doing raycasting and finding obstacles in a 3D environment.

I played company of heroes a lot and I never had the feeling that there is an actual grid underneath (correct me if I am wrong) since you could really freely move your units.

 

 

[jacquesr]

So I just found this. Looks interesting.

 

[mattstyles]

Sorry I didnt watch that video but that first image just shows a grid overlaying the obstacles. The reason grids are used is because path finding is traditionally expensive and using a grid can make it cheaper. A* isn't the cheapest algorithm but if you don't mind cutting corners then it can be made much cheaper, one cheap optimisation is simply limiting the number of squares available for a destination or increasing the size of the squares through which an entity can move.

In your case could you get away with creating a fairly fine grid, such that your users would maybe be fooled into thinking they had total control over where a unit moves to but in reality they don't? Each obstacle in your world could then be added to a grid tile that is overlaps, obviously a circular obstacle would not completely fill some squares but if your grid is granular enough then it would not matter. Granularity is the performance vs accuracy thing.

I've done obstacle avoidance (not path-finding) using all the obstacle primitives in a scene, but it wasn't very advanced and would not scale well—it only worked because the game world was small and the number of obstacles and entities were also fairly small.

The problem with raycasting would be that it assumes line of sight, you could extrapolate this out to something more A* like by casting rays from a point and attempting to collect a new set of weighted points from that cast, then repeat for all new points, using a similar heuristic-based method to A*, until you get to your destination. The set of points you would have would be far less than a grid-based one but the raycasting would probably be fairly expensive, it might also be fairly difficult to work out when a chain of points dead-ends. I'd be interested to see how that panned out if you tried to knock something up like that.

[jacquesr]

Thanks for your reply!

I think that in the end, also a vector /ray based algorithm would be mostly 2D, unless you 're trying to get a chopper from A to B through a city as fast as possible.

Maybe I will give it a shot. I also found this which looks interesting since it's polygon based:

http://codepen.io/AzazelN28/pen/ogeVKj

So for the map one could create a polygon based grid that has just enough tiles to have a fast algorithm that can find out dead ends and maybe then work with raycasting. Probably, a hybrid system can cover up for the inaccuracy of grid systems and the dead end problem with rayshots you mentioned.

Even if a natively running game can achieve a lot in realtime, we're still in javascript here and I guess we have to make simplifications/workarounds even with webworkers due to the nature of js performance.