Unknown Person was bugging me for help with a pathfinding problem for his game in wiz_chat. When he described the problem I realized I had already solved it awhile back so I gave him my old project. However upon looking at it it was quite a mess(as I never intended to actually release it or anything). So I checked to see if the problem could be handled via my new library and it couldn't without internal modification. So being nice I made new new version of the Dijkstra proc to return a list of all turfs that lead to and include the finishing condition turfs. This esentially lets you grab all turfs to a set finishing condition. Like in UPs case all turfs within a given movement range. However like I note in the update info it can be used for any number of things like getting all turfs accessable from a certain point without going over water or other obstructions.
So this should be a big help for anyone doing a turn based tactical game and want to display accessible tiles to the user!
http://developer.byond.com/hub/Theodis/Pathfinder
[Edit] And shortly after releasing the last version I start tinking with something else and realized I could use a version of my latest proc which only returned the datums meeting the finished criteria. So I tacked on another parameter which lets you decide if you want the interior datums, finished ones, or both.
ID:22368
 Nov 8 2006, 7:42 pm (Edited on Nov 8 2006, 8:28 pm)
|
|
|
Nov 8 2006, 8:14 pm
|
|
Elation
 |
This is pretty cool. Now I don't have to run A* for every tile around the unit; thanks Theodis!
|
Nice. I remember someone was working on a Shining Force clone, but cancelled development solely because there wasn't an algorithm that allowed them to perform the Shining Force movement system (if you weren't aware, has variable costs per tile and allows only orthogonal moves -- when your turn begins, it highlights all possible squares you can move into and allows you to move your character freely within them until you decide on a final location to place your character into).
| |
Yeah I played those game a lot awhile back so I'm certainly familiar :). Though the demo doesn't do it it is very easy to program the proc parameters to support this style of movement. Just rather than returning orange(src,1) like I do return a list a of the turfs in the orthogonal directions which are accessable and boom it hunts paths with no diagonals!
| |
I need to do some more complex demos. A* is very powerful and my library provides a very flexible bare bones version of it. So with the 2 procs you pass in you can have it solve for paths even given complex movement constraints on maps which may not even use turfs. While digging around when I just started getting active again I noticed someone needing a library for solving for paths in a mud which isn't constrained to a grid which my library is just perfect for :P.
| |
I love you Theodis. This makes my implementation of the movment system Jt described so much simpler.
| |
