Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (482)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (550)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Path finding  (Read 3335 times)
0 Members and 1 Guest are viewing this topic.
Offline CommanderKeith
« Posted 2008-11-20 05:45:34 »

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  Cool
Keith


Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2008-11-20 06:56:10 »

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).

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline phu004

JGO Coder


Medals: 4
Projects: 9
Exp: 10 years


NoSuchPersonException


« Reply #2 - Posted 2008-11-20 08:36:41 »

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!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #3 - Posted 2008-11-20 12:18:33 »

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!

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2008-11-20 13:07:38 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #5 - Posted 2008-11-20 13:23:29 »

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.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline kevglass

JGO Kernel


Medals: 153
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #6 - Posted 2008-11-20 14:37:29 »

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

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #7 - Posted 2008-11-20 18:01:53 »

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.

See my work:
OTC Software
Offline CommanderKeith
« Reply #8 - Posted 2008-11-21 07:22:13 »

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

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.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2008-11-21 08:19:36 »

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

The resulting shape is where the player can move.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #10 - Posted 2008-11-21 10:01:15 »

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. Smiley

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>.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline CommanderKeith
« Reply #11 - Posted 2008-11-21 16:30:49 »

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

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?!

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #12 - Posted 2008-11-21 18:13:13 »

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.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline CommanderKeith
« Reply #13 - Posted 2008-11-22 08:49:51 »

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.

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #14 - Posted 2008-11-22 13:51:12 »

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.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline CommanderKeith
« Reply #15 - Posted 2008-11-23 06:38:39 »

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

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CopyableCougar4 (13 views)
2014-08-22 19:31:30

atombrot (28 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (22 views)
2014-08-16 06:12:11

Rayexar (61 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (37 views)
2014-08-06 19:49:38
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!