Prev/Next Blog
by date

Grid map path finder for TGE

Name:	Jari
Date Posted:	Feb 17, 2008
Rating:	5.0 out of 5
Public:	YES
Comments:	YES
RSS Feed:	or Subscribe with .
Profile Page:	View profile page for Jari

Blog post

Hi, this is my first blog post.
I have been improving the pathfinding I used in one of my projects and extened it to 3D. It's AStar algorithm , basically, that operates on automatically built 3D grid map on terrain and interiors. So no need to place those nodes manually anymore.

Here's some screen shots for you to look:

img204.imageshack.us/my.php?image=screenshot00200001bc2.jpg
img257.imageshack.us/my.php?image=screenshot00200002vc8.jpg
Many houses, on top of eachother, large grid
Pathfinder Menu

I have also recorded some videos about the player walking though the grid when destination is selected by cliking. Maybe I'll post those later.

Videos:

www.youtube.com/watch?v=yx0l5S4dmMU
www.youtube.com/watch?v=NKzOJ6obihk
www.youtube.com/watch?v=M8rJZ2lU_ww

Submit your own resources!

Steve L (Feb 17, 2008 at 09:31 GMT) Resource Rating: 5

Wow, this is great. I can see a lot of uses for this. Would you consider releasing the code as a resource?

Clint Herron (Feb 17, 2008 at 11:09 GMT)

Look excellent, Jari!

Hans Cremers (Feb 17, 2008 at 11:24 GMT)

Ok got me intressted :)

H.W. Kim (Feb 17, 2008 at 12:47 GMT) Resource Rating: 5

Look great!

Matt Huston (Feb 17, 2008 at 13:39 GMT)

Very cool as there hasn't been a solution for building on interiors yet as far as I know.

Mike Rowley (Feb 17, 2008 at 16:08 GMT)

That looks really interesting.

Kyle Hagin (Feb 17, 2008 at 17:35 GMT)

Awesome!!! It would be really cool if you could release this as a resource. The interior solution looks great.

Ed Johnson (Feb 18, 2008 at 03:43 GMT)

Hey this looks cool. Throw my vote in for wanting to see this as a resource!

Edward Smith (Feb 18, 2008 at 04:01 GMT) Resource Rating: 5

Wow this looks great! Well done!

Jari (Feb 18, 2008 at 21:41 GMT)

Thanks. I was actually thinking of selling this, because there is quite a lot more than the grid but also the pathfinding and PathPlayer.

Jake T (Feb 19, 2008 at 03:21 GMT)

Hi Jari - can you post the video? I'd also be interested.

Ramen-sama (Feb 20, 2008 at 04:18 GMT)

Hows this different from the other gridbased pathfinding i've been seeing pop up lately?

Jari (Feb 20, 2008 at 07:15 GMT)

@Ramen-sama:
I assume that all the other pathfinding implementations require you to place the nodes (where the player travels) by hand in the editor. This does that automatically.

Ok here are the videos:

www.youtube.com/watch?v=yx0l5S4dmMU
www.youtube.com/watch?v=NKzOJ6obihk
www.youtube.com/watch?v=M8rJZ2lU_ww

And new screen shot:

Link
Edited on Feb 20, 2008 11:15 GMT

Chris Nehme (Feb 21, 2008 at 06:43 GMT)

Wow, that was awesome. Please sell it to us, lol.

Nice work, man. I'll buy one. :)

Jake T (Feb 21, 2008 at 23:47 GMT)

Agreed, videos look great Jari. I'm sure we could find ways to use it. Placing spawn points and nodes can be a pain, and our environment ends up looking so stale after a while without mixing it up. I'm thinking we could use something like this for vehicles if that would work - minus the stair climbing ;) Might work well with Andy Hawkins' wait/load system (?) - http://garagegames.com/blogs/31800/14254. This plus a good Boids/flocking resource would be great additions to the envirnoment pack imho. Let me know when you need an early purchaser/adopter/tester.

Devon Winter (Feb 27, 2008 at 02:51 GMT)

I'm curious -- are you putting every vertex on the open list, with a connection to every other vertex? Cause.. that's a lot of nodes! :)

Great work though!

Jari (Feb 27, 2008 at 21:22 GMT)

Devon, I'm not sure what is the open list, here, but you can define the grid size and also change the node placement radius.

Jason Gossiaux (Mar 06, 2008 at 03:29 GMT)

I've recently taken Ramen-sama's A* example and converted it into something very similar to what you are doing here. In my case I represent the terrain using a 2000x2000 grid. Early benchmarks show it just barely starts to hiccup with around 50 pathfindings of 100 nodes taking place simultaneously every 500ms on a 2Ghz processor. Have you done any benchmarking to see how well your implementation functions? I have several ideas for speeding the process up later.

Also, how did you get the node lines to render? I wrote my own fxRenderObject to draw paths, not nodes, but even that became very cumbersome. I had to store every vertex to be rendered as a persistant field, which was a lot of code since I don't think you can store arrays in a persistant field. So I have a whole mess of persistant fields for just 10 nodes... there is also the problem of having to make the renderobject's render box huge so the lines don't vanish when the object is out of sight. I'd love to know what route you took for the green node lines.

Good job with everything. It looks like it is shaping up well.

Jari (Mar 06, 2008 at 05:27 GMT)

Jason, I used an array to store the nodes. This is where the AStar operates and from where the points for rendering are fetched.
I have done speed tests but can't say much else than that it works for my game projects fast enough when I set limit for pathfinding nodes. Because the game it self is real time.

Jason Gossiaux (Mar 06, 2008 at 05:45 GMT)

So you were able to store an array in a persistant field? Or were you not using the concept of a render object to display the nodes to each connected client? If you know of a resouce displaying something similar I'd be happy to go check it out, I'm probably missing an obvious way of doing it without any hassel.

Jari (Mar 11, 2008 at 18:50 GMT)

Jason, the rendering is only needed for editing so they are just drawn from the one and only node stack.

Chris Nehme (Aug 13, 2008 at 01:12 GMT)

Just poppin' in to see if this is still coming? I hope it is... :)

You must be a member and be logged in to either append comments or rate this resource.