A* Pathfinding Demo

First thread :smiley:

Screenshot:
http://img62.imageshack.us/img62/107/pathfinderum9.th.jpg

.blend:

http://www.box.net/shared/e6djazh2nd

very interesting… what does the astar python module do?

it’s a thing i made to find a path between two points

sorry that I post only a wikipedia link:
EDIT: hmmm… link does not work. Search for “A*” at Wikipedia.

Hey scabootssca!

That pathfinding is completely awesome!! I tried to do something similar using an antrace algorithim but it just killed the framerate way too much and the code got so completely unwieldy it was a nightmare to debug.

This is exactly what I’ve been looking for, Thanks!:smiley:

How hard would it be to modify this to work in 3 dimensions? Ladders, ramps etc?

I had a quick look at your code but It’s a bit beyond me I think.:confused:

Thanks again!

Very cool!

The green cube seems to vibrate a bit when it’s moving, and there is sometimes a small lag after clicking space, but never the less, a very well done job.

very interesting… what does the astar python module do?

A* algorithm is when a node (in this case nodes will probably be generated at direction changes or when multiple paths can be taken) is given a value. The value will allow the heuristic to try and find the smallest value-number to the goal state, however the A* algorithm also implements distance from one node to another, and takes that into account when deciding which path to choose.

In short it finds the shortest distance possible from the start state to goal state.

Hey that’s cool :D, I actually made a somewhat complete ai module in blender 2.40 that had a* pathfinding and basic desicion making. It was fun but shortly after I left Blender game engine for Python-Ogre so I’d have more control and a more recent renderer.

you really rock at this, Nice work :slight_smile:

I wish I had you python scripting talent .

Thank you for sharing it with us :slight_smile:

Thanks to scabootssca sending me a copy of his code with more comments I have been able to modify it a bit.

This version has a z-axis as well. That is The path will be found whether it is North, South, East, West, Up or Down.

I have switched the blocks so that empty spaces are impassable and blocks form the path. Walls remain as walls.

(A moves red block up - Z moves it down.)

One thing I can’t figure out and if someone can it would be HUGE: scabootssca had a mechanism so that the bot did not cut corners. I can’t figure out how to make this happen with the z-axis as well… The bot find the path, but it cuts corners going up and down…

One other thing: does anyone know how you would go about changing the value (g cost) for different terrain types?

I hope this is helpful for others as well as me. Thanks.

Here’s the link:
http://www.4shared.com/file/23097941/ae4a0b40/astar-3d.html

Umm… is this verified and working for everyone else?

:rolleyes:scabootssca I think you might have switched up the destination and the start node in the Directions. It was actually the red piece that moves and the green one that doesn’t.

:(Sigh, I’m not sure what’s wrong with the file on my computer, it’s not really working. My error is attached below.

Attachments


Ya, funny it doesn’t work for mine either. weird…:confused:

you should have python I think

excuse me but i will post an actual job, it takes a time of today co-work and i will pay 100 bucks, its pain in the ass and dont trust me

what are you talking about ? a paid job for what ?