"Bald Eagle" <cre### [at] netscapenet> wrote:
> I'm currently testing a hierarchical method of maze-solving to simulate 1-way
> doors, and I've made some very small changes which have resulted in a massive
> slowdown - probably 1/8 to 1/10 the original speed.  :O
>
> All I've done is replace 5 lines where comparisons using = now use a <= or a >.
> The first slowdown was noticed by changing a single line from
> #if (walkability [a][b] != unwalkable)
> to
> #if (walkability [a][b] <= Threshold)

One of the things about trying to do stuff like this with a renderer rather than
a language where you can draw directly on the screen in real time is that you're
always working blind.   It's like playing a long game of chess, but you make all
of the moves in your mind, and then just set up the chess board in the final
configuration.

I do believe the problem lies not in the operator, but in the consequences of
changing the behaviour of the pathfinding algorithm when using the inequalities
that I've specified.

Last night I ran a 100-person evacuation simulation, and although I was
expecting it to take a full 40 min, it only took 25.
I had implemented a timer to see how long it took to solve each path, and most
of the paths too around 900 ms, but some took nearly 3 minutes!

So I'm thinking that maybe somehow the logic has changed in such a way that it's
ignoring obstacles when it shouldn't be.  And it occurred to me while walking
down a dark hallway, that when the algorithm is exploring potential directions
from a pixel, it has EIGHT directions to choose from, which coincidentally was
the rate of slowdown (on average, for 50 solves).

I'll have to give it some more mental chess consideration as well as think about
ways to get better feedback about what the algorithm is doing during the course
of its search.

Maybe pick one of the LONG path-finding points and trace out the entire search
path.

- BW

Post a reply to this message