Nodes slowdown issue: thoughts and conclusions

EDIT - Lag is now understood and largely eliminated. It's caused by some defective particle effects attached to some mobs.

After a certain investigation I've done on the issue of terrible slowdown and lag in the Nodes (e.g. Fire Node etc.), I came to certain rather unsatisfactory conclusions that, unfortunately, might ruin the hopes of many people here. I'd like to thank Steve Moret for helping me investigate this issue and for making important clarifications that helped understand the concept behind the slowdown issue.

So far, I know that:

1) The Nodes, essentially, are no different internally from any other map in the game. This, in its turn, means that:
1a) There is no specific code in the game that runs only for the Nodes and not for any other maps.
2) The main difference between the Nodes and the rest of the game maps lies in their outward design complexity. To quote Steve Moret, "The nodes are pockets of pathable areas connected by small pathways of pathable areas. And my guess is that finding that path along those little areas is making A* (the pathfinding algorithm) do nearly worst case every time."
3) Logically speaking, reducing the number of pathnodes for the Nodes maps (or removing the pathnodes at all) should help get rid of the lag and slowdowns, but it doesn't. The reasons for this are:
3a) The A* code in ToEE (the pathfinding algorithm) still performs crappy on short-distances, e.g. without the pathnodes at all, with the design of the Nodes in mind. This has to do with the way A* is coded, not with the way pathnodes are laid in the Nodes maps.
3b) It seems like the design intricacies of the maps (e.g. the fact that the Nodes are a collection of small joined pathable areas) make the code go into a rather long loop which causes the lag, which also has to do with the coding of A* and the design of the maps. Once again, this has little to do with the way pathnodes are laid in the Nodes maps.

So technically, we can say that while removing the pathnodes and the animated groundmesh (like Allyx did in his fix some time ago) might help reduce the overall lag or slowdowns, it doesn't fix the very essence of the problem, which is two-sided: it's the "incompatibility" of the A* code used in ToEE with the design chosen for the Nodes. Technically speaking, as long as the core of the problem isn't fixed, any player character or monster creature trying to use A* to path his way through the Nodes in a more or less complicated pattern may trigger the lag and slowdown effects due to the A* failing to find an optimal path even at a short distance. Therefore, to fix the lag once and for all, it seems that either:

1) The Nodes will have to be entirely re-designed (re-drawn and re-sectored) with the given A* peculiarities taken into consideration. Not the best way because, even if this is done, the Nodes will be completely different - like, more open, bigger areas joined with smaller corridors, probably.

2) The A* code will have to be rewritten or at least fixed so it works in a more optimized way. Of course, it's best to do this if you have the source code for the game. As you all know, we don't have the ToEE source so we can't do this, unless Spellslinger can work some magic here and fix it on the low Assembler level, which is going to be a very, very hard thing to do, I believe.

So this is where we stand right now, guys. Sorry this sounded disappointing, but that's sad truth, and at least we tried and we know what can technically be done, should the options be available to us in the future.

- Agetian

 

I'm fairly sure this news is disappointing to the community as a whole, but especially to me since I put so much work into experimenting and for the most part reducing lag in the nodes (by stripping out a lot of data that the nodes currently use). It is however encouraging to know that my attempt at reducing the lag only failed because of the hardcoded problems the game has had since it was created, and not something that I did that didn't work.

 

Mighty effort there Ag - gives us the theoretical underpinning for all the testing we did. Glad that was not in vain and the "i think its a pathnode issue" conclusions folks like Gaear and Al came up with was correct: its nice to know we weren't completely wasting our time.

Fixing it, on the other hand... :suprised: I got no idea.

 

Personally I don't like the signpost idea, rainbow rocks or not.

I put in a lot of effort to reduce the lag by removing the pathfinding file (which means traveling only short distances per click) and almost all special graphics (the swirley backgrounds etc...) and lighting files, the result is that in the fire node, lag was reduced from lengthy 10 - 15 minutes of lag each time, to at most about 30 seconds of lag.

At the time I suggested we fill the black background on the fire and air node maps with a non moving image similar (if not the same) as the animated version currently in the game, (Ted said he'd do this for me ).

While this is still not perfect (another workaround instead of a fix), I still beleive that this is the way forward as far as fixing the nodes is concerned.

 

I meant no offence Lord_Spike, I mod ToEE for my own enjoyment, if others feel they need to express thier appreciation, then I'm grateful for it, but I don't expect to be patted on the back by someone every 5 minutes either.

krunch, I don't think that would work at all. The way the paths are generated isn't worked out in the manner you describe...

The pathnode file lists the location of all pathnodes (points on the map) each pathnode within a 20 sector squared area are linked to eachother, so from the PC's start location the nearest pathnode is the first port of call, then the next pathnode in the direction of the destination point becomes the second port of call, and so on and so on until the closest pathnode to your destination point is reached.

If I still had the pathnode maps I made while creating the new pathnode files for the node maps I'd attach one, but they're long gone I'm afraid, but they look more like a spiders web - a line from one point (with a 20x20 sector square around it) to each other node within that square which also has the sector square around it etc, etc, until all of the area of the map that can be traversed is encapsulated within the sector squares.

I actually used 10 x 10 sector squares for the water node as there was a lot of zig-zaging around between nodes occuring.

 

Not sure if it will help any, but if the A star pathfinding algorithm used in ToEE is faulty, perhaps we can use the A star pathfinding algorithm as written in python instead?

Here's a link to the code. It will require someone much better at scripting than me to figure out if this stuff is even useful though.

There are other examples of Astar written in python on the web, just search for "python pathfinding algorithm"

 

Ahh, the day the English got lucky at Agincourt...

Ted DID do it, but forgot to post the files... :blush: