Sign in to follow this  
  • entries
    298
  • comments
    1135
  • views
    231310

A*: The (shortest) path to happiness.

Sign in to follow this  
HopeDagger

180 views

A* Pathfinding

So while working on the new enemies and their respective AI, I realized that the current 'pathfinding' is quite bad. Enemies just literally point themselves directly at you and charge. Not too exciting. We definitely need to get some pathfinding going on here.

Unfortunately I've never done real pathfinding before, so I nabbed Patrick Lester's wonderful article and got to work on a prototype using the splended C#+SDL.NET combination. Mix and boil for 2.5 hours -- minus some laundry-work here and there -- and voila! I was shocked at how easy it was compared to how difficult I imagined it would be. [smile]

Since we all love demos, I added a bit more user-friendliness and packaged it up for anyone who wants to toy with it. It's not boringly instantaneous; it actually step-by-step builds the path so you can see what's really going on.

You will need the .NET Framework 2.0 to run it, of course.

Left-Click: Add/remove walls.
Right-Click: Set start point.
Middle-Click: Set end point. (You need a 3-button mouse, sorry! [sad])
F: Calculate shortest path.
R: Reset map.

Download A* Pathfinding Demo







Now that I've got the concept under my belt, it's just a matter of reimplementing it in C++, and tuning it a whole bunch to work with a destructable environment. Should be interesting; both to write and test!

Maybe I'll play with flocking AI to see if I can build little sub-colonies of cells. [grin]
Sign in to follow this  


5 Comments


Recommended Comments

Thats pretty awesome, I always started A* projects, but I never follow through with them.

How are you going to "tile" your destructable landscape? I would imagine that making every pixel a tile would make the pathfinding rather expensive.

Share this comment


Link to comment
I'm not sure how much intelligence single celled organisms really need [smile].

I've played around with flocking AI in a few demos before and it's a fair bit of fun. I'm strongly considering using some low-level AI techniques in the same vein in my next game (been fleshing out some options in my head, although the fun of Membrane Massacre is strongly leaning me toward multi-directional shooters). I think flocking would work well with the cells in Membrane Massacre.

Share this comment


Link to comment
Very nice A* demo! It went the same way for me; I kept putting it off because I thought it'd be incredibly hard, but when I finally sat down and did it, it only took a few hours.

Share this comment


Link to comment
I got started by just bolting it right into Glow. [grin]

Yes, Glow has A* pathfinding. Not very obvious, is it? Ah well. Maybe future games will make better use of it.

Share this comment


Link to comment
That's awesome. Although yeah, I'm also wondering how granular you're going to make your tiles. I imagine you'll just have to try different sizes and see what works.

Keep it up dude! It's scary to think how cool this is going to be when you're finished!

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now