Prev/Next Blog
by date

A* Pathfinding stuffs

Name:	Ramen-sama
Date Posted:	Dec 25, 2007
Rating:	Not Rated
Public:	YES
Comments:	YES
RSS Feed:	or Subscribe with .
Profile Page:	View profile page for Ramen-sama

Blog post

So i'm rather bored and getting back to some pathfinding code for TGE. For my project i can't use pregenerated paths due to the fact this is for a battle system. With multiple characters moving around, can't have paths created ahead of time.

As stated in the title it's A* pathfinding using binary heaps. Currently you'll need to provide the code an array stating walkable areas and unwalkable areas, a start xy and end xy, and it will give you a path consisting of another array of sqaures that will be your path. From there you can dynamically generate a path using those squares converted to a vector to represent your "real world" coords.

I was curious how many people actually need such a setup? I may get around to releasing the code if others are interested.

[EDIT - Added Some Pics]

Here's some images of my nights work. It randomly generates an area of walkable, and not walkable areas. You can edit these as you wish with clicking and dragging. Then you enter pathfinding mode, where you click a start and end position. and wham. it generates a path.

So what use is this? well this grid i created was just for a personal graphical reference. But you can generate the "map data" from whatever method you choose to represent paths on whatever type of environment you are using.

So for me, i plan on having multiple characters running about, so for this to work well, i'd simply need to modify the map data each time a character moves to a new square. this way there won't be any intersecting paths between moving characters.

This pathfinding is very quick. my attempts at getting a time in MS just seems to give me a 0ms search time. maybe i'm doing it wrong.

subvoicestudios.com/~ramensama/Pathfinding_Test_1.0.zip

By default it will generate a map on it's own, and put you into pathfind mode, so you can start clicking and right clicking. if you want to modify the map, open the console and type PathFindMode();

Recent Blog Posts

List:	02/22/08 - Dynamic Attachment Update - Animated Environments 01/06/08 - Dynamic Attachment to objects 01/03/08 - 3D Painting with Modo 12/25/07 - A* Pathfinding stuffs 02/14/07 - More Platforms, works in 1.5 01/28/07 - Platforms Players can Ride Version 1.1 09/20/06 - Kork's Journey into Lightwave 3D 08/09/06 - More Lightwave stuff.

Submit your own resources!

Morrie (Dec 25, 2007 at 04:15 GMT)

I'm interested

Joe Rossi (Dec 25, 2007 at 05:48 GMT)

I'd like to see it!

Stefan Lundmark (Dec 25, 2007 at 17:21 GMT)

Quote:

This pathfinding is very quick. my attempts at getting a time in MS just seems to give me a 0ms search time. maybe i'm doing it wrong.

Get a higher resolution timer or profile it more than once. :) Same thing happened here.
Cool stuff you got there.
Edited on Dec 25, 2007 17:21 GMT

Joe Rossi (Dec 25, 2007 at 18:04 GMT)

There is an A* pathfinding resource for TGB that implements a version of A* on a TGB tilemap. I haven't tried it with the new version 1.6, but it compiled with 1.5. I remember people complaining about the performance, so if this can be applied to that and improve it, it would be awesome. I think a lot of TGB users could make use of this in their 2D games. I'll take a better look at the code when I get more free time. It seems very fast though. Thank you for sharing!

Here are some links for what we already have available:

Script implemented, slightly buggy, and not "true" A*
http://tdn.garagegames.com/wiki/TGB/Source/Pathfinding

"T2D" A-Star Pathfinding Extension
http://www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=9711

Ramen-sama (Dec 25, 2007 at 23:32 GMT)

I noticed the one for TGB before. But This is all TGE. its using code from http://www.policyalmanac.org/games/aStarTutorial.htm used with permission from the author for TGE. In his demo exe, the search time varies from 0-1ms as well.

subvoicestudios.com/~ramensama/PathfindSource.zip

Here are the two source file's you'd need to add to your own project.

My next step will be to figure out how to pathfinding with objecters larger then one square. Any ideas?
Edited on Dec 25, 2007 23:38 GMT

Ramen-sama (Dec 26, 2007 at 05:15 GMT)

w00t ok, i solved it! it can now do 2x2 searching on the same grid. For me, this was my end result i was aiming for from the begining.
Edited on Dec 27, 2007 22:52 GMT

Sean H. (Dec 26, 2007 at 15:49 GMT)

nice work on solving the problem Ramen. I know youve been at this for awhile.

maybe you could amend the algorithm to perform the single square search logic all the way up until you're near the destination so the character can still fit through narrow passage ways smaller than the destination object.
Edited on Dec 26, 2007 16:09 GMT

Orion Elenzil (Dec 27, 2007 at 21:37 GMT)

nice work as always, ramen.

> it can now do 2x2 searching on the same grid.

you mean the object finding a path is 2x2 ?

Ramen-sama (Dec 27, 2007 at 22:53 GMT)

How it works is that even "objects" that are 2x2 and 3x3 in size will still move along the path 1 square at a time, finding a path the size of the object.

What this means is you can pathfind a human to run across and create a 1 meter wide path, and maybe have a SUV also use the same map data and not hit anything
Edited on Dec 27, 2007 22:56 GMT

Orion Elenzil (Dec 27, 2007 at 23:11 GMT)

gotcha. cool. nice graphic by the way!

Ramen-sama (Dec 27, 2007 at 23:21 GMT)

if i could figure out the math to it, i'd do some path smoothing... but for now it'll do the job i need. Now i can have monsters of various sizes runnig around trying to kill me.

Ramen-sama (Dec 27, 2007 at 23:27 GMT)

Also, not that it's that important, but it supports saving and loading "maps" So you can visually edit these maps and save them for later. Still not sure if there's a point. i'd actually like to convert this into some 3d objects for the world editor or something maybe. My goal isn't so much as pathfinding across maps as it it to navigate other moving characters, so i guess i'd better go ahead and start testing.

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