Skip to main content

Find a Way - 0.01

A pathfinding demo demonstrating A*


Sean J McKiernan
(mekire)

This is a simple pathfinding demo that I made investigating A*.

 

Controls:

  • Mouse left button: add start/goal, draw barriers
  • Mouse right button: delete start/goal/barriers

(clicking the text on the screen triggers and toggles functions if you don't want to memorize hotkeys)

HotKeys:

  • Space: Start
  • Enter: Restart
  • i: Reset to initial state
  • 1,2,3: Switch between Rook, Queen, and Knight movement
  • d: Toggle animation on/off
  • Esc: Quit

Links

Home Page
http://code.google.com/p/find-a-way/
Source
http://code.google.com/p/find-a-way/downloads/list

Releases

Find a Way 0.01 — 3 Dec, 2011

Find a Way Recode — 24 Jun, 2013

Pygame.org account Comments

  • Ppaterson 2011-12-03 17:49:04

    Very cool.

    You might also want to check out networkx. I have been using this in a couple of my games and it is very fast and flexible. You make a graph of your 'board' and then use the shortest path functions to find a path, either weighted or not.

    I can share some code if you are interested.

    Paul

    Mekire 2011-12-04 07:21:04

    Thank you.  As for networkx it sounds interesting but I am somewhat hesitant to include dependencies that would require additional installation by users unless absolutely necessary.

    -Mek

    Paul Paterson 2011-12-05 00:02:25

    Yes, I know what you mean. It is a tough trade-off. I have the same concerns, although networkx can be installed with easy_install so that makes it a bit easier.

    Jouni Järvinen 2011-12-07 09:55:20

    Nothing needed to install assuming you can add the code directly into the program.

  • Gamer90030 2013-07-05 20:04:17

    AGH WHY IS EVERYTHING A ZIP FILE I CAN'T OPEN ZIP FILES D:

    Mekire 2013-07-08 00:20:41

    Seriously? It would take you two seconds googling to find a program that can unzip for you, if indeed you really can't do it.

    If you REALLY can't unzip a zip under any circumstance then copy the code from the repository. >.>
    http://code.google.com/p/find-...

    -Mek

    Gamer90030 2013-07-08 02:18:40

    Pretty much all programs I Google are viruses. It's hard to find the right thing out there.

    Jouni Järvinen 2013-07-05 20:26:11

    Why's that ?

    Gamer90030 2013-07-06 15:30:05

    My computer doesn't have the right app or whatever. When I try to open them, my computer says that I don't have the right app to support them.

    Jouni Järvinen 2013-07-06 18:25:57

    Now that's weird in the least. AFAIR Window$ had integrated ZIP support since XP and all Linux desktop distros have that, and I'm sure even MacOS had integrated ZIP support since long time ago. Anyway, get 7-Zip, best of all compression programs (and really free unlike WinRAR which doesn't even support everything), and its native format 7z using the LZMA2 algorithm is the best out there; You can use 7-Zip on non-Window$ systems too using http://www.winehq.org/ but I dunno how to get Wine onto OSX. However, I'd recommend making a TAR file if you're compressing many files and then compressing it using XZ is the best choice especially for UNIX/Linux users. Alot of work, but worth it, especially since 7z tends to corrupt and when it does the data is 100% lost.

    From http://sourceforge.net/project...
    - 7z922-x64.msi for 64-bit Window$
    - 7z922.msi for 32-bit Window$
    - 7z922-arm.exe for Window$ Mobile and Window$ CE

    And remember to configure the thing ! Again assuming you're running VI$TA or newer, right-click on the shortcut, goto 'Compatibility' tab, click 'Select options for all users' and tick 'Run as Administrator', to make it possible to always use the File Manager even when U(ser) A(ccount) C(ontrol) is enabled, assuming it's conffed. ZoltanSoftware has a guide for 7-Zip but it's -old-: http://rautamiekka.org/zoltans...

    Gamer90030 2013-07-07 04:00:41

    I did not get a word you said. I can't get 7z cuz I dont' know how! I've tried, but I never found one that's not a virus...

  • MentalAtrophy 2014-02-11 06:49:12

    Hey, mate, is it cool if I incorporate your solver module into one of my projects and modify the heuristics? I've done some testing with it already and it works really well for real-time pathfinding of multiple entities if I throttle the number of Star.evaluate() calls based on the total number of entities that are actively updating their pathfinding.

    Edit: Nevermind, I made my own anyway. I borrowed your idea of separating the search into its own evaluate() method though, because I liked that instead of burying the whole thing in a while loop.

    Mekire 2014-02-22 14:49:43

    Seems like you solved your problem already, but yes, feel free to use it for anything you desire. I'm sure it can still be more efficient.
    -Mek

  • Real name 2017-08-30 13:35:23.353640

    IDK how to build A* pathfinder (I got 3 versions, and three of them don't works)