ID:1271061
 
BYOND Version:499.1185
Operating System:Windows 7 Pro 64-bit
Web Browser:Chrome 26.0.1410.64
Applies to:DM Language
Status: Open

Issue hasn't been assigned a status value.
http://www.candlelitgames.com/pathfinder_src.zip

Run the demo.
Click stats panel to see stats.
Click once on a turf.
Run away from the black dots, and try to run from them for as long as possible (but keep them on screen). It might take up to 60 seconds before the slow down begins to occur.
Eventually, the game will slow to almost a grinding halt, yet the cpu stays the same. If you observe the memory with task manager, you'll notice it doesn't increase much, either.

To see what's happening, look in pathfinder.dm

Summary: The internal pathfinding has a leak of some sort.
In Eternia, and I assume other projects, this has a major impact on public quests where there's a fair amount of mobs chasing...

Hoping to see this fixed soon. Seems pretty nasty.
Normally I would point to a call stack issue from the user, but this is something I've personally dealt with and can say that no matter how hard I try to clear the call stack, it does no good. This is why I don't use BYOND's A* pathfinding function, walk_to().
In response to Solomn Architect
Solomn Architect wrote:
Normally I would point to a call stack issue from the user, but this is something I've personally dealt with and can say that no matter how hard I try to clear the call stack, it does no good. This is why I don't use BYOND's A* pathfinding function, walk_to().

Yeah, I've tried all kinds of quirky loops... nothing works.

I can't imagine a byte-code version of the A* being faster than what they can pull off internally... in fact there's some sort of internal tracking of density that we don't have access to (for example, it will avoid dense mobs, but if we wanted a custom pathfinding algorithm to do that we'd have to scan through the contents of a turf first where their pathfinding is obviously not doing that).
It wouldn't, obviously, but doing it manually would at least ensure that it gets done without creating a stack leak. I would create the algorithm to not worry about dense mobs unless they bump into one. In that case, restart the algorithm but add the turf that the mob tried to enter into the dense list. However to account for crowds where there may not be a way through to the path, you could go ahead and check for dense mobs for the rest of the algorithm.

It would lose a bit of speed if the mob hit something dense, but that speed loss would only be situational and not default for the process, thus creating a nice middle-ground in terms of speed and efficiency.
In response to Solomn Architect
Solomn Architect wrote:
It wouldn't, obviously, but doing it manually would at least ensure that it gets done without creating a stack leak. I would create the algorithm to not worry about dense mobs unless they bump into one. In that case, restart the algorithm but add the turf that the mob tried to enter into the dense list. However to account for crowds where there may not be a way through to the path, you could go ahead and check for dense mobs for the rest of the algorithm.

It would lose a bit of speed if the mob hit something dense, but that speed loss would only be situational and not default for the process, thus creating a nice middle-ground in terms of speed and efficiency.

Great points, but ultimately, there should not be a stack leak and hence, step_to / walk_to is broken.
True. An internal fix would be optimum.
After a lot of messing around and trying home-made pathfinders, bypassing Move() / Enter() / Exit() and other things... I noticed something... I was setting glide_size for each atom moving on every single successful move. Once I removed the glide_size change and continued to set location manually, the performance definitely improves a lot. So this definitely has to do with a combination of internal pathfinding, animate_movement, and gliding.

You can get 3000 atoms to step_rand() no problem (while changing glide_size on every move). But you can't use get_step_to, get_step_towards, step_to, step_towards, walk_to, walk_towards on more than 100 mobs for more than 30 seconds without locking up the server.
It's always something stupid like that! I hate that so much. You work so hard on trying to fix something when it wasn't even that something to begin with >.<
In response to Solomn Architect
Solomn Architect wrote:
It's always something stupid like that! I hate that so much. You work so hard on trying to fix something when it wasn't even that something to begin with >.<

No, there is still a problem. You should be able to set glide_size on every move (like when speed changes, or you go diagonal). Perhaps you missed my point, I can set 3000 glide_size settings in a single tick just fine, but why can't I do it when I'm using pathfinding?

This is still broken.

Let me further the cause... So we say the internal pathfinding is broken, ok that's fine lets make our own. I did and the same problem occurred. Ok, let's not use any Move(), step(), Enter/Exit and just purely set x and y... Did that, and guess what, the problem is still there... Let's finally remove glide_size settings, and now the problem is better (while not totally gone, performance is OK).

It needs to be possible to change glide_size for tile-based games in order to look smooth and to have a speed system. Otherwise, everything moves at the same speed and there's no movement dynamics, and AI is stupid.
I've discovered some more things:

Calling step_to and walk(ref, 0) on the same atom in the same tick doesn't clear the "stack"...

Calling walk(ref, 0) and then waiting a tick to step will clear the "stack" allowing things to calm down / recharge and jittery goes away.

This sorta works, but we're off by a tick_lag 50% of the time...
mob/proc/movement_loop()
if(!loc) return
if(world.time >= move_time)
if(!target)
for(var/player/p in world)
if(get_dist(p, src) <= 10)
target = p
break
else
if(rand(0, 1))
walk(src, 0)
else
step_to(src, target)


spawn(world.tick_lag) movement_loop()


However, this does not work...

mob/proc/movement_loop()
if(!loc) return
if(world.time >= move_time)
if(!target)
for(var/player/p in world)
if(get_dist(p, src) <= 10)
target = p
break
else

walk(src, 0)

spawn(world.tick_lag) step_to(src, target)


spawn(world.tick_lag) movement_loop()
More stuff:

Ok this whole time, I've been testing in visible range. Tried spreading out "fake players" and "fake monsters chasing the fake players" all over the world, and there was no slow downs. It seems, this has to do with how much a client can see on his screen at one time, and the hundreds / thousands of glide_size calls happening within that screen within a second of time.

Test players and test mobs are non-dense.
Right. So are there thousands of calls made off screen while you're running this on-screen test? If not, the famous "Don't do anything until there's someone around to see it." way of calling loops would be most efficient.
In response to Solomn Architect
Solomn Architect wrote:
Right. So are there thousands of calls made off screen while you're running this on-screen test? If not, the famous "Don't do anything until there's someone around to see it." way of calling loops would be most efficient.

I've spoken to Lummox JR about this off the forums, and its something to be looked at, but not right now as there are other more important issues at hand.

The problem is that seeker should be able to handle that many updates but it's only able to take it after several calls fail (the step_to's reach their destination for longer than tick_lag). You can get around this by just using Move(get_step_to()) and delaying the next try upon fail, and make sure you test with density on!
Galactic Soldier wrote:
This doesn't seem to happen when the world is hosted on Dream Daemon and you're connected under local host, only when it's ran entirely off Dream Seeker. Also, I didn't find the problem to be exclusive to glide_size change.

Good to know, I'll have to try it out like this too.
It does work better as dream daemon is hosted. This probably isn't much to worry about because this much stress should be hosted by Daemon instance instead of seeker.
Galactic Soldier wrote:
Oh and by the way, you're performing calculations wrong in this as well. It's almost like you make guesses until it works, but when it comes down to it there's another method that yields a faster and more accurate result in different circumstances.

What on earth are you talking about? lol. The code is to forcefully make dreamseeker mess up, not to write a game.
In response to FIREking
FIREking wrote:
Galactic Soldier wrote:
Oh and by the way, you're performing calculations wrong in this as well. It's almost like you make guesses until it works, but when it comes down to it there's another method that yields a faster and more accurate result in different circumstances.

What on earth are you talking about? lol. The code is to forcefully make dreamseeker mess up, not to write a game.

And yes I realize x / 2 isn't exactly the same as x >> 1 or x * 0.5 depending on integer or float
I assume this is still an issue? Because the problem still persists in my project.
This issue exists when you run a server and seeker client in the same thread (ie: hitting "run" in dream maker).

To avoid this issue, always use dream daemon to test your game.
Page: 1 2