ID:1265045
 
Applies to:DM Language
Status: Open

Issue hasn't been assigned a status value.
I am requesting that walk_to respects return value of Enter() when "taking obstacles into account". Currently, it only looks at density.

If the a* point system is used, you could just have it take notice of return value and when a 0 is returned, the grid of available non-blocking tiles is manually updated as such.
This would make walk_to() significantly slower, as it would be calling Enter() for every turf it considered. Density is used as a shorthand precisely because it's easier to handle.

All things considered, I'd actually prefer to make the walk_to() routine even better by using its current shorthand behavior, but keeping better track of open areas. If open areas are broken into discrete rectangular units and the places they touch, then travel can be calculated based on the ability to enter and exit through those regions, and the algorithm would require fewer steps. (The only difficult part is handling regions that are too narrow in one direction, but amply wide enough in another. The trick there is just determining which spaces the walker can occupy.)
Here's a lot of stuff on the Jump Point Search method which is one of the fastest, http://www.gamedev.net/topic/ 626654-understanding-the-jump-point-search-algorithm/

Jump Point calculates this spiral maze in only 234 iterations / less than 1 ms vs 3861 of A*: http://imgur.com/a/alFZX

Now that I think about it, calling Enter() would be a bad idea, because it could cause code to execute that shouldn't (some developers have used Enter to cause things to happen as opposed to answering the question we're asking, can we enter?) or just require developers to use Enter() as intended.

I can't think of an elegant solution except for my specific case, it would be the ability to call check_can_enter(atom) when checking for each tile to be included in the possible tiles allowing movement.

I do think we need something more than just density, at least at call time. Perhaps a "variable" name could be supplied for checking, or a list of variables for factoring if tile in question should be included or ignored.
Considering how walk_to() uses significantly less network bandwidth than repeated calls to step(), I'd say making it slightly more CPU-intensive for a boost in functionality is well worth it. If calling Enter() breaks anything then it's the developer's own fault for using it incorrectly as that's why we have Enter() and Entered().

Perhaps this feature request should be changed to, "can we get some powerful, native pathfinding processes for use in online games?"
In response to SuperAntx
SuperAntx wrote:
Considering how walk_to() uses significantly less network bandwidth than repeated calls to step(), I'd say making it slightly more CPU-intensive for a boost in functionality is well worth it. If calling Enter() breaks anything then it's the developer's own fault for using it incorrectly as that's why we have Enter() and Entered().

Perhaps this feature request should be changed to, "can we get some powerful, native pathfinding processes for use in online games?"

My gripe with Enter() use is still valid, because of situations like this...

turf/cave/Enter(atom/a)
if(isplayer(a) && a:level<3)
a << "You're not ready yet."
else
return ..()


So the walk_to would be checking to see if monster is a player or not while its pathfinding which is sort of a weird design.
In response to Lummox JR
Lummox JR wrote:
This would make walk_to() significantly slower, as it would be calling Enter() for every turf it considered. Density is used as a shorthand precisely because it's easier to handle.

All things considered, I'd actually prefer to make the walk_to() routine even better by using its current shorthand behavior, but keeping better track of open areas. If open areas are broken into discrete rectangular units and the places they touch, then travel can be calculated based on the ability to enter and exit through those regions, and the algorithm would require fewer steps. (The only difficult part is handling regions that are too narrow in one direction, but amply wide enough in another. The trick there is just determining which spaces the walker can occupy.)

I am now curious if walk_to uses step_to, and if so, is step_to recalculating the entire path every time it is called. I noticed when calling walk_to once and then modifying the terrain afterwards, the more efficient path was recalculated and used automatically. This is why I believe walk_to is using step_to, and that step_to is calculating the best path every time it is called.

I'm just curious as to what your approach was because I need to model it almost exactly the same, but just add support for looking at more than just density.
In response to FIREking
Ah, you're right. While I like the idea of a check_can_enter() proc, it really seems like it's just a duplicate of Enter(). Though, I can't think of a better alternative either.

Would it be too much to ask for procs like a_star(Ref,Trg,Min,Lag,Speed) and jump_point(Ref,Trg,Min,Lag,Speed) which checked tile contents as well as just tile density by default? It would be really awesome to have more robust built-in pathfinding.
In response to SuperAntx
SuperAntx wrote:
Ah, you're right. While I like the idea of a check_can_enter() proc, it really seems like it's just a duplicate of Enter(). Though, I can't think of a better alternative either.

Would it be too much to ask for procs like a_star(Ref,Trg,Min,Lag,Speed) and jump_point(Ref,Trg,Min,Lag,Speed) which checked tile contents as well as just tile density by default? It would be really awesome to have more robust built-in pathfinding.

Yes, this is exactly what I am really asking for. I'm sure they want to improve it, but the execution might be difficult as I'm sure BYOND isn't easy to change at its core.

I have been playing around with movement loops and efficiency of calling the loop at only the fastest speed a mob is allowed to move, and gaining performance that way. I can get 3000 mobs awake at once, no problem. But that's just a constant custom _step_rand, and not pathfinding. Next: implement jump point into my system to see how well it performs.

Edit: I did think of something a little less limiting... you can ignore density for players but enforce it for AI, which enables pathfinding to work as intended, and allows more complex situations for players (like directional blocking) The only problem is, the AI would completely ignore this directional blocking and we're back to "having a dumb AI". It would work for a lot of simple games, though, and still offer the possibility of directional blocking to anything controlled by a client.

We still need a way to influence the scoring of tiles for the built in pathfinding, or provided with some helper procs to build our own systems without having to put the pathfinding in the byte code.