Monday, April 26, 2010

Pathfinder Example

Ever wondered how your troops, tanks or heroes find their way on the map of a RTS game? Or why they get stuck or change their direction every move? I did and decided to find out and program a pathfinder myself. I implemented the A* pathfinding algorithm. My implementation is not very efficient (I know how to make it more efficient), but does work. It's not very special and something most n00b programmers have probably done, but I want to share it anyway as it gives a more satisfactory ending to my little Sunday afternoon project. I also want to know if it runs on other computers, so it would be cool if some of you could try it. No need to install anything (at least, that's what I hope), just unzip and run the exe. I can't compile it for OSX, because I need a Mac for that.
Controls: 
q = quit
r = reset/restart
space = start/pause path finding
left mouse = add water/wall
right mouse = remove water/wall
Settings: Edit settings.txt

Download: 
PathFinder for Windows XP/Vista/7
PathFinder for Ubuntu x86 (Linux binary)
at

8 comments:

  1. cybrbeast26 April, 2010 17:15

    It works, but it crashes if there is no possible path.
    I wonder why some games still suffer from bad pathfinding.

    ReplyDelete
  2. pimp-a-lot bear26 April, 2010 17:56

    It works on my ubuntu laptop as wel as on a windows xp-64 bit machine.

    I took a course on routing algorithms a few years ago and the A* algorithm. Perhaps it's time to implement it before I start forgetting it all. Problem is the lack proper programming skills. What would be a good language for developping my programming skills?

    Anyway, now you've implemented the shortest path problem, you could start solving the Travelling Salesman Problem :P

    ReplyDelete
  3. cybrbeast26 April, 2010 19:33

    Nice programming btw, I liked paying with the algorithm. You're really becomming a coding geek now :P

    ReplyDelete
  4. Kamiel26 April, 2010 20:26

    Cool stuf, it works here aswell ! Wouldn't it work almost twice asfast if you start from the end point with searching aswell?

    ReplyDelete
  5. annom28 April, 2010 04:37

    Thank you for testing! Very good to hear it works on both linux and windows.

    I'm not sure how this would work if you start searching from the others side as well. Good idea though. It will be hard to make a smart method that runs from both sides and meet at some point. Two independent searches from both sides will be twice as slow, although there is possible that a path is found earlier.

    I gave the travelling salesman problem a try, without searching for conventional ways, just trying my own ant like path finder. I have ants running over my screen, but I want them to make a scent trail and this doesn't work all that well yet.

    A good language for developing your programming skills is probably Python. It is what got me started. It really depends on what you want to do with it though and what you want to learn. Python is easy because it does not care about a lot of special things you have to take care of in static languages like C, C++ or Java. It assumes a lot of things that are correct most of the time, but this can also cause weird errors and instability etc.

    Java is the modern C++; something in between C++ and Python. It can do almost everything and runs on most systems and OSes because it runs on an extra layer, the Java virtual machine that is available on almost any system. This makes it slower than C or C++, although it is catching up. And you can ignore this for most applications.

    Python, Java and C++ are all object oriented languages. You really have to learn the basics about this if you want to write more than a few lines of code. An example is a car class, the blue print of a car. In your program you can then create multiple car objects from this class and use them independently. You can combine objects, inherit from other objects and communicate between objects to make complex systems out of simple systems. It is a very powerful concept and almost every modern program uses this.

    C++ is basically the object oriented version of C and also completely supports C.

    C++ has the steepest learning curve of the languages mentioned, but will learn you most about how a computer works under the hood. It is also the language (with C) used in most science and engineering applications.

    Then there is also C# (C-sharp). It is the newest popular language and should be like C++ and Java, but better. It will probably replace Java in the future as most popular language. I have no experience with C#.

    So pick Python if you just want to play. The concepts transfer to other languages so it's not wasted time whatever language you pick.

    ReplyDelete
  6. cybrbeast28 April, 2010 13:34

    Thanks for the tips, though I think I'll prefer playing games to programming for fun (for now) :)

    ReplyDelete
  7. pimp-a-lot bear28 April, 2010 13:49

    Thanks for the overview! Sounds like python is the place to start.

    Here is the course material on routing algorithms. There's also a section about bidirectional search of the A* algorithm.

    ReplyDelete
  8. annom28 April, 2010 15:16

    :) I answered pimp's question, not pushing you into programming.

    I'm only evangelical about open source software and (anti)software patents.

    ReplyDelete