Avoiding specific Nodes

[Yonaba]

Could be an interesting feature to be added to the pathfinder class. Sometimes, we do want to avoid some specific nodes without marking them as unwalkable. I am thinking of adding those methods to the API:

pathfinder:setAvoidance(f)
pathfinder:unsetAvoidance()

Typically, a function will be passed to the former method. That function will be called on each node to check whether or not the node should be ignored from the search. The given function should be prototyped as specified below, and will return a boolean.

function f(node, ...) ... end

[mtdowling]

+1. This would be great. I currently am running into an issue in a tile based game where I want to path find to a node that isn't walkable, but attempting to walk into the node is the desired behavior (e.g., walking into a tavern increases health but the player can't actually walk through a tavern).

[vadi2]

You also want to allow avoiding edges along with nodes. I've run into practical examples where you, for example, don't want to completely block a room off (because it has several other exits that you do want to use) but just a particular exit between two rooms (it's temporarily inaccessible or you don't want to walk through there).

[Yonaba]

@mtdowling , @vadi2 : Can you please provide some sketches explaining the problem you are running into and the expected behaviour ? It'll help, thanks.

[vadi2]

In my case I'm using an existing pathfinding system that's been developed and improved through the needs of players - we found that in practice, we need all of:

a) room-based locking: for when a room should not be entered into (you enter and die, for example, or it is enemy territory) b) exits-based locking: particular exits can be disabled in a case where the logic dictates that you don't want to lock a room but a particular exit is unavailable, for example there is a door that you haven't got a key for c) room-based weighting: some rooms take longer to cross than others (for example, a wading through a river - you'd rather pick 3 land tiles than 1 river tile) d) exit-based weighting: some exits can be slower to traverse than others, for example there is rubble in them.

[Yonaba]

Thanks for all those details @vadi2,

a) Room-based locking Should't this be solved by setting the underlying tiles as unwalkable ?

b) Exits-based locking This is something I tried in the past. I wanted to see if was possible to pathfind with nodes that have specific rules for crossing: for instances, tiles that can only be entered from the north, etc. I implemented it via bitmasks (with this approach), but the result was not much satisfying, and most of al, it was not working really well (I think I did not investigated it well enough, though). But I am willing to reconsider the problem (see #21). Hopefully, that will work.

c) Room-based weighting, d) Exit-based weighting It reminds me of a features I wanted to take a look at (#9) and I feel like it potentially solves this. I wanted to include weighting for nodes. Actually, adding a weight value to a node is supposed to increade the penalty for going through that node. So that the pathfinder will attempt to avoid this very node without completely ignoring it. I actually implemented it already (as a side experiment in a different branch, but the intent was to provide a simple solution to avoid stacking when routing a group of agents). You can take a look at it here, and there's also a video available.

[vadi2]

(a) probably is, I included it for completeness.

The rest of the stuff is interesting - when I'll have time, I'll try using jumper out in Mudlet (mudlet.org). It's a C++ MUD client embedding Lua for scripting. Pathfinding is handled on the C++ side by Boost's A* implementation, with a rich API available to Lua (http://wiki.mudlet.org/w/Manual:Mapper_Functions). The map data is stored on the C++ side but every detail is retrievable in Lua, so you can in effect pull all the data out and use your own pathfinding algorithms - making it possible to play with Jumper in it.