search

adventuregamestudio / ags

AGS editor and engine source code
Other
695 stars 159 forks source link

Optimise pathfinder syncing with room masks #894

Open ghost opened 5 years ago

ghost commented 5 years ago

Noticed by @ericoporto , new pathfinder apparently has to sync with room masks each time path search is called: https://github.com/adventuregamestudio/ags/blob/master/Engine/ac/route_finder.cpp#L60

The operation is not that slow because it does not copy pixel data but scanline pointers. Still I guess this may be optimized by making engine notify pathfinder module when mask has changed.

From the top of my head:

ericoporto commented 4 years ago

I think a character or object that is solid, when moved, also edits the walkable area. So maybe the walkable area would need a bit to mark it as edited/dirty until the walkable is synced.

ericoporto commented 3 weeks ago

Unfortunately the code has been refactored and the link on top is now invalid, but as far as I can tell the problem remain. I wonder if an option to ignore solid characters/object game wide could work here, because then you just need to resync the walkable area once if there was a change in the mask.

ivan-mogilko commented 3 weeks ago

There are two problems here, unfortunately I did not mention one all of them when writing this ticket in the past:

  1. copying of scanline pointers is one thing. This actually should not be too slow, it's copying number of pointers == height of bitmap.
  2. rebuilding of navigation grid. I never investigated that, but I suspect that this might be a relatively slow operation.

Enabling/Disabling of walkable areas is a relatively rare, infrequent operation and should not cause much issues. It is moving solid entities that "cut holes" in walkable area that may affect its performance most.

So if performance is an issue, this system has to be rather looked on from this perspective.

Like i said, I did not investigate how the grid is generated yet, and I do not have a clear vision of how it may handle moving objects. But here's a vague idea I have in my head:

Right now the cut parts are passed through a conversion between walkable mask (bitmap pixels) and navigation grid. Because of that they cannot be handled individually by the pathfinder, and it have to recreate all grid from mask every time. If instead each solid object would register itself in a pathfinder, and pass its "collider" settings individually, the pathfinder maybe could use that to adjust the pregenerated navigation grid in related parts only.