A* Pathfinding Demo

Game Engine Game Engine Resources
#1

Hey.

Here’s my A* Pathfinding demo.

Basically, here’s what goes down:
You click to set a destination marker, which the little red guy will quickly pathfind around blue obstacles to get to. The pathfinder is 3D capable, so there are a couple obstacles that you can tell the little red guy to go on top of (there’s a picture of this below). You can now also rotate the camera with arrow keys to help get a perspective on the 3D stuff.

Below the images there’s a quotebox with more detailed information about the pathfinder. Also, the scripts are very well commented, so you might have a chance at figuring out what’s what. You can use any part of this demo in any way you want.

Download:
>> Pathfinder3.blend.zip (Right-Click, Save-As)

Images so you know what you’re getting into:
http://img155.imageshack.us/img155/2762/pathfinderscreenie.jpg
http://img512.imageshack.us/img512/3241/pathfinder3.jpg

More Details:
(This isn’t a quote at all, I’m just using this quotebox to separate this information from the rest of the post)

Alright, so basically, the pathfinder object finds a path given a starting position, target position, and a list of node objects. This list of node objects is generated (once at the beginning of the scene) from what I call a “nodemesh string”. A nodemesh string is a big string of information that is generated based on the vertices and edges of a mesh called the nodemesh. The script that generates the nodemesh string information is called the “nodemeshCompiler”, and it is a blender script.

I’m getting the feeling that you are very confused about this.

I guess you could say that it consists of three primary components:

  • The Pathfinder
  • The Path Follower
  • The Nodemesh Stuff

So, in order to change the obstacle layout, you need to:
1) Change the obstacle layout.
2) Change the nodemesh (on layer 3) to match your layout.
3) Generate the nodemesh information with nodemeshCompiler.py (press ALT+P in it’s window).
4) Copy and paste the information from the console (new: or from the file “NODEMESH.txt” that the script saved to your computer when you weren’t looking), to the “nodemesh” variable in “slab.py”.

Alright, well, I’m sure some of you might have a very vague idea of what is going on, and that the vast majority of you are completely confused.
Either way, the file itself contains more information that may help.

If you’ve got any question or comments or whatever, post them here.
-Chaser

#2

ha ha! Nice man! That must of taken hours to make, (it would of taken me 5 years) 0.o. How can people customize it, I don’t understand how…

EDIT: Nvm, just read the first little part of this thread :smiley:

Nice job m8
Linkxgl

#3

Cool. I will probably use this at some point, maybe I’ll try it out for my current project.

#4

Wow, thats the best pathfinding demo Ive seen in the BGE, you’ve really done some nice work here Chaser.

Would it be hard to randomize the path the character takes? Seems to always take the shortest route.

Great work however, this is very very useful!

#5

thanks very useful, not sure if Electronic Arts Research is going to publish their on path finding or not but as long as it isn’t hardcoded yet, I’ll be using this script ^^

thanks

#6

Nice work, Chaser. :smiley:

I’ll probably need this very soon, so I appreciate you sharing it.

Yep. A* is defined as an algorithm which finds the “least-cost path” between nodes. “Least-cost path” could potentially include factors other than distance (like the amount of possible detriment to the NPC), but generally it just means shortest route.

#7

Hey.
Thanks for the comments and stuff.

The following updates have been made:

  • Little red guy’s physics have been redone (no longer can go through walls, will bounce off walls if he does collide)
  • 3D elements added (a couple obstacles have ramps)
  • Code comments improved
  • More information and instructions included in “info.txt”

Download:
>> Pathfinder2.blend.zip

The first post in this thread has been updated to reflect the changes (it will be kept up-to-date).

I’m planning to making an improvement to the pathfinder tomorrow.
-Chaser

#8

i click and nothing happens.

#9

really cool

#10

amazing, im gona try and implement this into a little mingame

#11

Thats really neat. I thought about using meshes for A* (nav meshes are the proper term I think) but could never really think of how to work it. I’m going to take a look at how you’ve done it.

Thanks

#12

At #4 in your post you said you have to copy and paste the information from the console. How so you do that? Or did you mean copying it all down by hand and then putting it into the script?

#13

Wow great scripts!

@nemitis: I can’t copy from my console either, also it doesn’t store enough history for the output. Looks like I would have to just write the node compiler output to a file.

#14

Thanks for bringing the copying issue to my attention. I’m on a Mac, and I can just copy and paste it. I’m going to release an update sooner or later, and it will allow the nodemeshCompiler’s output to go to a file or something, along with an update to the pathfinder itself.
-Chaser

#15

Amazing. Best pathfinding in the BGE.

#16

Some of the commercial engines out there don’t even have built in pathfinding so this is pretty big news. The script rox.

#17

I know. This made my day.

#18

I’m going to guess that those having issues copying from the console are probably Windows users (Mac and Linux have better terminals :wink: ).

Now, to copy from the windows console, you either have to right-click (doesn’t always work) or click the console window’s icon and go to edit. From there, select mark and highlight the text you want. Then hit enter to copy it to the clipboard, and paste it where you want.

You can also output the stuff from the console to a text file. Hit windows+r and type in “cmd” and hit enter. Now, use cd to navigate to the blend file. If it was on my desktop, I’d use:

cd C:\Users\Moguri\Desktop

Now, assuming Blender is installed in the default directory:

"C:\Program Files\Blender Foundation\Blender\blender.exe" Pathfinder2.blend > log.txt

I hope that helps people out. By the way Chaser, this is pretty cool :smiley:

#19

Hey everybody.
I’ve updated the demo.

Changes:

  • Inner workings of the pathfinder have been optimized and/or made more accurate
  • The nodemeshCompiler script outputs to the console, AND outputs to a file (“NODEMESH.txt”)
  • There are now two pathfinding methods, “findPath” and “fastFindPath” (this demo is set to fastFindPath).
  • You can change the camera’s view with the arrowkeys.
  • I’ve added an orange transparent bridge that goes over a part of the map (to test more 3D capabilities)
  • Code commenting and info.txt slightly improved

Download:
Pathfinder3.blend.zip (Right-Click, Save-As)

Thanks for the comments,
-Chaser

#20

What’s the difference between pathfind and FastPathfind?