[Request] Distance\path search algorithm

Has anyone developed a path search algorithm such as A* algorithm or Dijkstra's algorithm to calculate the distance moved between two point while moving around or avoiding obstacles\impassable terrain? I was wanting to enforce a movement restriction script so that a token could not move past its set movement speed, but in order to do that I need to be able calculate the distance traveled moving around walls and what have you.

I wrote the initial version for the Hero Engine . =D I've considered a similar system for the API here. The primary trouble would be how to mark difficult terrain, impassible boundaries, or boundaries that have a different cost based on direction (going down off a small cliff is regular movement but up is difficult terrain). Then figuring different types of movement (climbing down, flying, blinking, a spider's movement over it's web, etc.), dynamically changing conditions (breaking a wall opens a new route, cave collapse closes a route, spell makes difficult terrain, spell changes movement types, etc) ... it's a difficult problem. I'm happy to help work on it though!

I guess my question would be how simplistic would you like to keep this. Initially I would keep it as simple as possible and when a PC moves it doesn't really "enforce" movement but rather whispers the GM that a token moved from X loc to Y loc (Z movement cost) and let the GM rule if the movement was acceptable or not. This would allow is to implement something useable while allowing for more complicated and accurate logic later. Sounds like the problem is properly "flagging" a terrain either with its boundary type or movement cost. Since I would prefer to set these properties at design time rather than run-time I would (at least initially) ignore vertical movement since there is not a good way to really keep track of Z axis movement or directional conditions. I.E climbing a 100 foot cliff as difficult terrain takes X moves, however jumping off it takes 1. I'd rather try and tackle that later if at all =P. I would also make the assumption that all tokens on the object layer count as an impassible boundary unless you are flying. I know that's not exactly accurate as a creature can move through other named or mook tokens based on the size of the two tokens, but again I rather not get into that initially. On the topic of how to flag map tokens based on terrain type, I believe the naming of a token would suffice for this. The logic would enumerate through all map tiles and build a collection of boundaries. I see a few possible naming conventions for this. From easiest to most complex 1) Fixed names which associate it with a specific cost Tile Name: Wall - This title will always be impassable and added as a boundary blocker Tile Name: Wall* - This title will always be impassable unless your token is flagged as flying with 'wing' counter Tile Name: Difficult - Passable but counts as double movement Tile Name: Difficult* - Passable but counts as double movement unless your are flying anything else would be normal cost 2) Including an optional "property tag" to the end of the name setting the movement cost per square to enter the tile. Tile Name: Wall_Cost:30 - Climbable wall which cost you 30 feet\units to enter Tile Name: Wall_Cost:9999 - Impassible barrier Tile Name: Anything_Cost:10 - Difficult terrain (since it cost 2x) 3) Combining a set of property tags such as cost/square (above) with other calculations such as height. This would allow you to take some liberties such as calculating movement to\from height based terrain (I.E Moving from a lower to a higher terrain cost 2x movement but moving from higher to lower cost 1x). This seems overly complex however and I think keeping up with with would be more than its worth since we do not have a good way to track and represent someones movement along the Z axis. I'm open for suggestions.

Aaron said: I wrote the initial version for the Hero Engine . =D I've considered a similar system for the API here. The primary trouble would be how to mark difficult terrain, impassible boundaries, or boundaries that have a different cost based on direction (going down off a small cliff is regular movement but up is difficult terrain). Then figuring different types of movement (climbing down, flying, blinking, a spider's movement over it's web, etc.), dynamically changing conditions (breaking a wall opens a new route, cave collapse closes a route, spell makes difficult terrain, spell changes movement types, etc) ... it's a difficult problem. I'm happy to help work on it though! Paths placed below the jpg map on the map layer... different color = different terrain... would be one way. Draw them above first.... so they align on your jpg map and its easier to draw.. then pull the jpg map forward and all the information needed is below and the API can read it just fine. Keeps your GM, Dynamic lighting and token layer free.... while giving you a pseudo layer under the jpg map.

Aaron, Do you already have some starting base pseudocode for the formulas\methods? I'll start working on some basis point and if you have anything to assist in jump starting it I would be most obliged.

Not in JavaScript. :) I'm working on a script to help one of my players who is basically blind understand the terrain via text description. Most of what I've done in this regard is thinking about isolating squares/points that are in the same section of dynamic lighting, and determining line of sight so they can be announced to him. In my case, I was considering preprocessing maps for this information based on the dynamic light boundaries I generate (see my walls script).

Aaron, I'll take a reference to anything you have that you think might be helpful regardless of language. I can adapt it. I expanded my utilDistance.js script to include a function to calculate proper DnD based movement cost given a waypoint path. <a href="https://app.roll20.net/forum/post/1178655/script-d" rel="nofollow">https://app.roll20.net/forum/post/1178655/script-d</a>... I will dive in to the real meat and potatoes soon (hopefully) to properly modify a tokens waypoint when moved so it avoids obstacles between waypoint nodes. Once the waypoint is modified it can be passed in to my distanceOfPathInUnits function to get the proper distance in feet\units.

Here's a pretty nifty site for path planning in JavaScript: <a href="http://qiao.github.io/PathFinding.js/visual/" rel="nofollow">http://qiao.github.io/PathFinding.js/visual/</a> Here is the source: <a href="https://github.com/qiao/PathFinding.js" rel="nofollow">https://github.com/qiao/PathFinding.js</a> And the A* algorithm: <a href="https://github.com/qiao/PathFinding.js/blob/master" rel="nofollow">https://github.com/qiao/PathFinding.js/blob/master</a>... Honestly, the algorithm is the easy part. Building the graph is the hard part, from the perspective of doing this on Roll20. I've got a few ideas about ways to do that, but Stephen's idea about drawing lines and burying them under the map might be the easiest.

Here is a very much still a work in progress start. There is no A* methods yet, this is initially a script to define map boundary types per page. I am making the assumption that map token boundaries are static enabling me to pre-build all the boundaries for performance reasons. I thought enumerating over every token every time someone moves would create a potentially dreadful wait times while it calculates. I have added a Loc (a pixel defined set of x,y coords) and Node (pixel x,y coords of the center of a square belonging to any given Loc) class to my utilDistance script found here. I just updated it and I have noticed there is a long delay between when I update a Gist and when the updated code is reflected here on the forum, but it should come through eventually =) <a href="https://app.roll20.net/forum/post/1178655/script-d" rel="nofollow">https://app.roll20.net/forum/post/1178655/script-d</a>... Gist: <a href="https://gist.github.com/ce4b8b1a8c98f445ae2b.git" rel="nofollow">https://gist.github.com/ce4b8b1a8c98f445ae2b.git</a>

Gists are cached. To get them to update, you need to edit the link and add an anchor to the end. I use a version number: ....ae2b.git#v1.