Small pathfinding glitches

[Bertram25]

Not linked to the latest PR (merged or unmerged), here is what I've found:

Both when playing the 'Scream in The Dark...' map:

• A worker gets stuck in idle mode when digging top-left of the map. It is 100% reproducible. Have a look at the light blue team workers.
  
• Workers have a hard time going through L like corridors:
  
  The bug is also systematic in this map. First the workers will claim the map without any problems. then, once they will try to go through that part, they will be stuck going left - right, left - right within the two tiles of the lower part of the L corridor.
  When they are chased, fighting or something else, they aren't stuck anymore. Until they come back here, and get stuck again...

[oyvindln]

I am planning to look at the pathfinding function more in detail in general, so I will have a look at it later if someone hasn't fixed it by then.

[hwoarangmy]

This may be linked to floodfill (if the tile the worker gets on is not well floodfilled) or to the creature behaviour also.
@oyvindln if you decide to fix this, please assign the issue to yourself before doing so or give a word here so we don't end up doing the same :)

[oyvindln]

@hwoarangmy I will do that if I start working on it.

[oyvindln]

For the second error I think it could have something to do with the creatures in idle mode only looking at visible tiles. They are supposed to walk to a random tile nearby, but I'm not sure if the random function is very good.

[hwoarangmy]

I've already seen that the visible tile calculation is pretty restrictive. As you say, in such a case, I guess that the visible tile list may be empty (or maybe just the tile where the creature is). That would explain why...

[Bertram25]

As I could have bet, that one is the next most annoying thing on the list, IMHO.
I'd propose to test this change:
Have a new sight algorithm taking in account all tiles in the creature sight (default 15 tiles around it but configurable.) and not only the ones not hidden by walls.
And rename the current one for visible tiles only if the name isn't fitting already.

Then, I'd use the new unrestricted algorithm for pathfinding, digging and such, and the restricted one for enemy creatures/traps/enemy rooms scans.

What do you think, guys?

[oyvindln]

That sounds good.

[Bertram25]

Ok, I'll have a look. ;)

[hwoarangmy]

Again, I've not checked but the more I think about it, the more I'm sure it is because the visible tiles list is empty. So, if it is the case, it will be a clever way to overcome this.
And if it is not, you will have to debug ^^

[Bertram25]

And if it is not, you will have to debug ^^

Eh eh. :)

[hwoarangmy]

While I'm thinking about it, I think there is a problem with the visible tile computation. If you start the skirmish test map 2v2 and destroy one tile (releasing the dragon) he will take ages to come to your dungeon. Normally, as soon as it is in the line between the wall, it should see the dungeon heart and attack...
And that's the same for your screenshots. In your cases, the visible tiles should not be empty...

[Bertram25]

@hwoarangmy Oh ok, I'll use this case to quick-test.

[oyvindln]

One issue in the worker movement algorithm is that it tries to make the worker move to far away visible tiles, by sorting tiles by distance, and choosing a random tile from the furthest away half of the visible tiles list. When there are only 2 visible tiles, this could potentially make the worker go back and forth alternating between two tiles if nothing else is visible. The fact that random function we are using is rather basic (look in Random.cpp) may also be an issue when there are few tiles to choose from.

[akien-mga]

One issue in the worker movement algorithm is that it tries to make the worker move to far away visible tiles, by sorting tiles by distance, and choosing a random tile from the furthest away half of the visible tiles list.

Is this also the reason why workers tend to go back and forth when claiming walls (they claim a wall tile on one wall, then run to another wall and claim a tile, then back to the first to claim a tile in the neighbourhood, then to another wall, etc.? This can easily be seen when digging a big rectangular room.

[oyvindln]

That may be, I thought they were supposed to check nearby tiles for work first though. The moving far away bit part is for choosing random tiles to walk to if they are idle.

[hwoarangmy]

Maybe the surrounding tiles are not considered visible. That would explain why they claim far away walls instead of nearby...

[akien-mga]

To illustrate my above comment, here is a picture showing in which order a kobold claimed wall tiles. You will also notice the fact that workers tend to claim every other wall tile before they claim the the remaining wall tiles (making it look like a chessboard). I can infer that most likely they do not see the tiles that are adjacent and parallel to the one they just claimed (it works well in angles, as the 2->3 path shows on my screenshot).

[Bertram25]

@akien-mga I'm sure you got a bug, but as far as I've looked, the workers blocked in corners bug seems to indeed come from the gamemap->visibleTiles() function that is listing only tiles within view and probably broken for a few use cases.

I'll be working on that one now as it's quite interesting. :) As a first step, I must say that swapping this method with one returning any tile within sight radius is easy and I'll make tries using that change.

[Danimal696]

while creatures train they dont stop jumping from machine to machine, maybe its related?

[akien-mga]

@akien-mga I'm sure you got a bug, [...]

You mean I'd better open another issue, since this one is more about the corner issue?

[Bertram25]

You mean I'd better open another issue, since this one is more about the corner issue?

IMHO yes. :)

[hwoarangmy]

while creatures train they dont stop jumping from machine to machine, maybe its related?

No. Creatures training are handled by the training hall. But each turn they have a chance to change dummies. It might happen too often. I will add min and max turn numbers for changing dummies the room config file in #239

[Danimal696]

yes, its too often, they hit two times at most and then switch machine

[Bertram25]

Base issue fixed with #281 Other issues have been opened for the other problems. :)