Idea for performance tuning

[originalfoo]

Note: This is based on my somewhat vague comprehension of how pathfinding, etc., is working.

Have a status byte on each lane? (not sure of correct terminology) which can be used to determine what additional checks might be required when that lane is being considered for a route:

• 1 = some customisations present (see other bits to determine which)
• 2 = speed customisation
• 4 = vehicle customisation
• 8 = intersection lane routing

Unrelated to pathfinding:

• 16 = emergency protocol (see later)

So in the pathfinder, it could quickly work out if it needs to do additional checks (is first bit set or not) and if not skip all the more advanced logic.

From what I can see the vast majority of intersections/lanes within a city are not T++ customised, people tend to be using them in mostly localised fashion to deal with specific traffic issues, so skipping extended logic should have a noticeable affect on performance?

Emergency Protocol

I threw this in randomly above... Idea is that if an emergency mode (flashing lights) vehicle is about to enter a segment, the emergency protocol bit is set on the relevant lane. AIs processing vehicles on that lane would instruct them to make way for the emergency vehicle:

• vehicles pull to side of road as if parking/delivering/collecting (should already be code in AI for this sort of movement?)
• vehicles also removed from 'the grid' – not sure of correct term; but ARIS Enhanced Hearse AI does something like this to prevent Hearses collecting dead from blocking traffic

The result is that vehicles move out of the way to let the emergency vehicle through. Could even go so far as to alert upcoming intersections to gain temporary 'right of way' for next leg of route.

[joaofarias]

I was thinking about using the first bit but I hadn't thought of the others. Nice thinking! Thanks :)

Regarding the emergency protocol, I want to do something like that in the future but I do believe I'll need to change the method that is used by TM for the traffic lights and priority roads, making the mods incompatible again - the same thing happened with the speeds but I found a way of not touching that method, so I might find a way here too.

[originalfoo]

Not sure if this is related or not: https://forum.paradoxplaza.com/forum/index.php?threads/simulation-slows-down-then-freezes.858733/

Edit: Might be caused by All 25 Tiles Purchasable mod: https://forum.paradoxplaza.com/forum/index.php?threads/simulation-lag.859080/

[joaofarias]

I don't have that mod and I can reproduce performance issues.

[joaofarias]

Just a quick update on how performance is going. There's more stuff to improve and still a lot of work to do, but in what regards the pathfinding, I'm not sure I can improve it much more. I still have some stuff I want to try but I'm not sure it will produce noticeable results. I just did a quick test and I got the following results:

The test was done in a 65k population city, with about 20k lanes - which is what actually matters for the pathfinding - averaging the time taken to calculate each path after 10,000 paths.

	Vanilla Pathfinding	Current Pathfinding	New Pathfinding
ms/path	1.8581 ms	4.2928 ms	2.3158 ms
x Vanilla	-	2.3x	1.25x

[originalfoo]

Still a huge improvement! :D

I was pondering earlier today... the more intersection route customisations and lane vehicle restrictions that are applied, the faster the pathfinding should become (due to potential routes being ruled out sooner)?

[originalfoo]

BTW, when you save "averaging the time taken" I assume there are some outliers in the mix? Paths that take far longer than usual to calculate... if so, shrinking those would yield a big improvement?

[originalfoo]

Defaulting all segment intersections to ahead+adjacent only should drastically cut down on possible paths, no?

Also, what about caching small sequences of lanes based on traffic density and/or lane speed (traffic drawn to fastest lanes)?

[originalfoo]

...you could potentially cache sequences of nodes between intersections. So from start of a lane (at an intersection) to all destinations of that lane (factoring in segment intersection lane changes) at the next intersection. And include in that data the speed of that sequence + which vehicles can use it if possible.

Path finder main task is find route A to B, then fastest of those routes, with some randomisation. So it's doing lots of work following nodes that don't get to B... make that part faster. Once it's got a list of valid paths, it finds fastest two routes and randomly chooses one of them. It then 'decompresses' the cached chunks within the route to get the full set of nodes on the path.

Whenever road changes are made, work out which lanes are affected, and which subsequent intersections lead to those lanes in order to invalidate/refresh those items in the cache, etc.

Quite a bit of work, but should in theory lead to a decent performance increase.

[originalfoo]

...caching could be done incrementally in a thread: each time a chunk of route is cached, set a bit on the relevant start node to indicate that node now has a cache available.

[joaofarias]

the more intersection route customisations and lane vehicle restrictions that are applied, the faster the pathfinding should become (due to potential routes being ruled out sooner)?

Yes.

when you save "averaging the time taken" I assume there are some outliers in the mix? Paths that take far longer than usual to calculate... if so, shrinking those would yield a big improvement?

But there are also very short paths. After 10,000 paths, I'm sure they balanced each other.

Defaulting all segment intersections to ahead+adjacent only should drastically cut down on possible paths, no?

Not necessarily. Imagine a car in the rightmost lane of a normal 6-lane (It just came out of parking, for example). The car wants to turn left on the next intersection, so it needs to move to the leftmost lane, but there's only 1 lane changing intersection. If you only allow ahead or adjacent, the car can't move to the leftmost lane and is forced to do a much bigger trip, consequently causing the pathfinding to take longer.

Also, what about caching small sequences of lanes based on traffic density and/or lane speed (traffic drawn to fastest lanes)?

What if the destination is within that cache? You can't simply skip pieces of road that are potential targets.

Path finder main task is find route A to B, then fastest of those routes, with some randomisation. Once it's got a list of valid paths, it finds fastest two routes and randomly chooses one of them.

The pathfinding does not find multiple paths and chooses one. It finds one and that's it - it's guaranteed to be the fastest (if it wasn't randomized). The randomization happens during the algorithm. Every lane will have a value used by the algorithm to compare them wich each other. It's this value that is randomized just a bit so that the algorithm doens't always choose the fastest route - it's being tricked into choosing a lane thinking it is the fastest, when it might not be.

So it's doing lots of work following nodes that don't get to B...

The algorithm is heavily optimized to not waste time here, already.

[originalfoo]

re: ahead+adjacent only...

Not necessarily. Imagine a car in the rightmost lane of a normal 6-lane (It just came out of parking, for example).

Good point, although you've picked the worst case scenario which is also probably quite rare. In a big city, what percentage of roads are 1way 6lanes?

The number of lanes that can be crossed at an invisible intersection could be based on the number of lanes the road has in a given direction:

max_lane_cross = Math.max(3, Math.floor(num_lanes_in_direction / 2));

I have no idea what C# functions are available so above is Javascript/Ecmascript.

The max_lane_cross would be calculated for each direction of each prefab and cached for that prefab.

IMHO if it's not a massive butthurt to implement, it would be worth at least testing. As an initial test just hardcode in to the pathfinder a static ahead+adjacent only default rule (for un-customised segment intersections) and see what that does to the average timings for 10k paths.

Also, I think end users would appreciate less drastic lane crossings on the bigger roads; there's a constant trickle of screenshots decrying >1 lane crossings, particularly on highways.

[originalfoo]

The pathfinding does not find multiple paths and chooses one. It finds one and that's it ...

If looking at the pathfinder as a black box, yes, it returns a single path that's the fastest (-ish, taking in to account randomisation).

Internally though, it must be trying different routes - this is my current comprehension of how it works (which is probably wrong in many aspects):

• From starting point, find some lanes in general direction of target
• Starting with the fastest lane, repeat first step with current lane as starting point
  • if can't use it, go back to step 2 and try with next lane in the list

What would a more detailed / correct description look like?

[joaofarias]

Sorry for taking so long and thank you for answering to everyone on steam. I've been really busy this weekend.

I wasn't talking about 1-ways. Any road with 3 lanes going the same way would cause that problem.

I think adding that rule would make things worse as it's another check that not only prevents optimal paths from being found in some cases (causing more calculations) but also is only used in three types of roads - 6-lane 2-way, 6-lane 1-way and highway.

The algorithm is a bit hard to explain. If you want to read on it - it's a lot to read, though - I recommend this: http://theory.stanford.edu/~amitp/GameProgramming/ Wikipedia also has some stuff (search for A*) and a couple nice animations that show you how the algorithm branches out to find the best path.

[originalfoo]

Thanks for infos :)

Recent forum topic about performance issues, will post update to user after next release. http://steamcommunity.com/workshop/filedetails/discussion/409184143/615086038679099781/

[originalfoo]

Regarding vehicle restrictions, would it be worth making them 'softer' - so instead of a solid block on vehicles accessing a lane, it would be speed based; in the pathfinder a restricted lane would return a very low speed for a vehicle that's not allowed on it.

This would mean, for example, that if cargo isn't allowed on the inside lane it would still be able to use it but only when absolutely essential to make deliveries. Having made the delivery it will quickly vacate the lane to get to a faster one (the slowness of the lane for restricted vehicle would only exist in the pathfinder; the vehicle AI would operate at normal speed as defined by vehicle prefab and lane speed settings).

As the pathfinder will try fastest lanes first, it shouldn't have too much of an impact on performance (as the super-slow restricted lanes will only be tested as last resort)?

This could fix, for example, issues with large road + bus lanes next to a cargo station.

[originalfoo]

As city population grows, particularly over 55k, speed buff mass transit routes in the pathfinder (buses, metro and trains) = less agents on the roads...?

[joaofarias]

The softer restrictions might be a very good solution, even more so for the problem I'm having with vehicles giving way to emergency vehicles in those rare cases where there are emergency vehicles in all lanes, resulting in vehicles having no lane to go to and despawning or making a u-turn.

I'll run some tests with it. See how it behaves.

Speed buff is cheating and the amount of buffing we can do before buses start to go out of their lanes in corners will only delay the inevitable for a few thousand citizens.

[originalfoo]

For the Masshole feature, is there a way to throttle it if CPU is struggling, or maybe limit number of massholes per game tick? In some tests I'm getting visual stuttering most likely due to too many vehicles in traffic jams trying to find new paths at the same time. Or maybe it's thread locking somewhere?

[originalfoo]

Would it be worth tweaking the HumanAI so that as a city grows (or if game is lagging - is there any way to detect?) the pedestrians do less of their random movements (eg. stretching arms or crouching down etc)...? Just thinking of anything that might reduce CPU load...

[originalfoo]

Regarding softer restrictions, would it be possible to create some 'leakage' to any lanes that connect to the restricted lane (if those lanes don't connect onwards to any other lanes)? For example, if you have a lane that restricts cargo, any lanes that lead to that lane would have slightly slower cargo speed to discourage the pathfinder from considering them as a cargo through route...?

[originalfoo]

Just linking tickets that will be affected if "soft" vehicle restrictions approach is used:

• 55 (possibly fix)

• 26 and #41 (should fix)

• 27 (might affect).

[originalfoo]

There have been lots of reports about fps issues over the last week, not all of them relating to T++ but quite a few were. IMHO it would be good idea to have the Massholes AI as an optional feature so people can turn it off if their game is lagging too much. I realise you're probably putting throttling stuff in to scale back the more complex stuff as city grows, but even with that it would still be useful to completely turn off the Masshole AI that deals with vehicles that are about to despawn.

[joaofarias]

I am reviewing every single class in the mod to try and optimize it, taking the opportunity to also improve some rough edges. The options manager/panel was one of them and it now allows every single feature of the mod to be disabled, including each individual change to the AI. ;)

[originalfoo]

OMG, nice! Won't that in itself cause some performance issues though (eg. all the extra checks as to whether features are enabled)?

[joaofarias]

There aren't enough options to make it significant. Plus, they're simple boolean comparisons (which are pretty much negligible on their own) so it will need a ton of options to have any impact.

[originalfoo]

Would it be possible to make small percentage (15%?) of masshole drivers ignore lane restrictions and lane routing when pathfinding to avoid despawn? Would be like a "road rage" feature, but more importantly reduce pathfinding overheads that result from traffic jams. Could also decrease happiness of the driver :)