Path finding

[CommanderKeith]

Hi,

I need to figure out some path-finding code for a non-tile based 2d top-down view game, where obstacles are polygons. The moving player can be treated as a polygon, a circle or a point.

The game is a point-and-click diablo-style game. I'm hoping that with good path-finding code I won't need any collision detection. The path-finding can ignore moving obstacles like other players.

When faced with this problem, have you found it best to make your own custom path-finding solution by studying A* etc or is there something out there that's standard?

Thanks 
Keith

[Riven]

Make a grid, and fill the cells by 'drawing' your polygons into it.

Now you can perform regular pathfinding on the grid.

The size of the gridcells will determine the accuracy, and calculation time, so you can make the cellsize variable, depending on ... whatever you think it should depend on (CPU speed, time left, priority, etc).

[phu004]

There is no path finding in diablo man. Remember in act 3, the final boss - mephisto could easily get stucked in the corner.  I believe if your goal is to make a similar game to diablo,
some cleverly tweaked immediate obstacles detection is sufficent. Yeah there will be monsters stuck behind the walls, but they might just appear to wait there for
an ambush if you have the fog of war enabled.

Games published by our own members! Check 'em out!

[CommanderKeith]

Make a grid, and fill the cells by 'drawing' your polygons into it.

Now you can perform regular pathfinding on the grid.

The size of the gridcells will determine the accuracy, and calculation time, so you can make the cellsize variable, depending on ... whatever you think it should depend on (CPU speed, time left, priority, etc).

Good idea, that sounds pretty simple!

The thing is, I'd like to keep the movement non-tile-based. So when the player clicks on some random point, I'll try and make him go straight to that point if possible rather than zig-zagging to the middle of each tile on his way to that point... Should work. thanks

There is no path finding in diablo man. Remember in act 3, the final boss - mephisto could easily get stucked in the corner.  I believe if your goal is to make a similar game to diablo,
some cleverly tweaked immediate obstacles detection is sufficent. Yeah there will be monsters stuck behind the walls, but they might just appear to wait there for
an ambush if you have the fog of war enabled.

Hmm, ok, but I thought that the player definitely had path-finding, because he seemed to be able to find his way around things. Well it was a long time ago when I played diablo!

It's funny that you mention fog of war, I'm going to need that too! I suppose the grid answer is also suitable? I remember Kev Glass did some work on it in his recent game and he kindly described his technique so I'll dig that up from his blog.

Thanks for the help guys!

[Riven]

Good idea, that sounds pretty simple!

The thing is, I'd like to keep the movement non-tile-based. So when the player clicks on some random point, I'll try and make him go straight to that point if possible rather than zig-zagging to the middle of each tile on his way to that point... Should work. thanks

The grid is only used to determine whether or not the target is reachable. Once you find a path, you can more or less create your own line/spline through it, removing 'redundant' waypoints.

[Orangy Tang]

If you've got polygon input/world rather than tiles then converting to do tiles to do pathfinding isn't particularly great IMHO. Instead you should break down your walkable areas into a network of convex hulls (probably at compile time or level load time). Then run A* over this network and you'll get a series of hulls to walk through, and since they're convex you can get from any point in a hull to any other point by just going in a straight line, resulting in a very efficient and natural path.

Most 3d games do pathfinding like this, not only does it scale well to work regardless of level geometry or tile resolution it'll be more efficient (space and CPU time) since large empty areas can be represented by a few convex hulls rather than a whole heap of empty tiles.

[kevglass]

Here's a couple of blog entries I did when I was recently doing something similar to what Orangy said:

http://www.cokeandcode.com/node/1282

http://www.cokeandcode.com/node/1289

Intead of convex hulls I just built the biggest rectangular regions I could, mostly because I could see how to do it without any effort. I bit of smoothing and optimisation later and I had my squad patrolling the hulk. I think it'd adapt to 3D also.

Kev

[Eli Delventhal]

You can also just do a sort of pseudo-quad-tree approach. Have a very non-precise grid, path find through that, then path find through that grid divided into 4, etc. until you're basically down to the pixel level. Reasonably fast, looks natural, and is very easy to implement.

[CommanderKeith]

Thanks heaps everyone, you're advice and links are really helpful 

I like the simplicity of the tile approach, and it seems quite similar to Kev's rectangular hulls way if I were to combine tiles that aren't needed. So maybe I might do that.

I'm just thinking out loud, but is there an easy way to take player width into account with the convex hulls approach? It seems like most approaches treat the player as a point, so he can fit through very small gaps even when he's too fat. With the tile-based approach I could just make the min tile width bigger than the player width I suppose.

[Riven]

If the shape is convex, you can extend all faces by the player's radius.

The resulting shape is where the player can move.

Games published by our own members! Check 'em out!

[Orangy Tang]

If the shape is convex, you can extend all faces by the player's radius.

The resulting shape is where the player can move.

MDK did that and it's a nice idea, unfortunately it all fell apart when they came to do the sequel and had three very differently sized characters (and so would have had to store three different versions of the nav mesh).

Since we're in 2d we can cheat - all you really need to do it compare the player size against the length of the segment joining the hulls (which can be precalculated). Plug that into A* to restrict which nodes you search over and you're done.

Since building the nav mesh can be done totally offline you can recruit some heavier maths library to give you a hand, like <a href="http://www.vividsolutions.com/jts/jtshome.htm">JTS</a>.

[CommanderKeith]

This is great guys, thanks for those pointers. That's a pretty neat and easy solution 

Since building the nav mesh can be done totally offline you can recruit some heavier maths library to give you a hand, like <a href="http://www.vividsolutions.com/jts/jtshome.htm">JTS</a>.

I had a look at JTS, but how exactly will it help? Can it build a nav mesh for me?!

[Orangy Tang]

I had a look at JTS, but how exactly will it help? Can it build a nav mesh for me?!

It's a low-level polygon/topography API, so it's not going to do the work for you, but it provides nice operations like creating polygons from line segments and doing set operations (union/intersection/and/or) between polygons and a whole lot of other stuff. If you were to use  Riven's method of shrinking/growing the areas based on a radius then that's a built in operation too.

[CommanderKeith]

Cool, that's useful. I've still got to figure out how to make convex hulls out of the polygons. Seems like JTS can only make convex hulls fit around polygons rather than make a polygon into an array of convex hulls. Maybe I'll find a way to triangulate the polygons, or use quads like kev does. Then i have to make the triangles/quads into a tree somehow i suppose so A* can work on it.

[Orangy Tang]

Yeah that's the one thing I found was missing too. Slick has a method for converting simple polygons to triangles though, that might be a useful starting point.

[CommanderKeith]

Thanks, actually I notice that Kev has some pathfinding code in the slick distribution as well, so that's pretty cool.