nextStep can return -1 in Monster.c:2020

[krypt-n]

Hi,

I built BrogueCE with -fsanitize=undefined and noticed the following errors:

src/brogue/Monsters.c:2021:34: runtime error: index -1 out of bounds for type 'const short [8][2]'
    #0 0x55acec595c28 in pathTowardCreature /home/mfunk/src/BrogueCE/src/brogue/Monsters.c:2021:34
    #1 0x55acec5afd1a in monstersTurn /home/mfunk/src/BrogueCE/src/brogue/Monsters.c:3351:17
    #2 0x55acec64955e in playerTurnEnded /home/mfunk/src/BrogueCE/src/brogue/Time.c:2410:25
    #3 0x55acec5c1926 in playerMoves /home/mfunk/src/BrogueCE/src/brogue/Movement.c
    #4 0x55acec4e37b6 in executeKeystroke /home/mfunk/src/BrogueCE/src/brogue/IO.c:2592:13
    #5 0x55acec561241 in mainBrogueJunction /home/mfunk/src/BrogueCE/src/brogue/MainMenu.c:852:25
    #6 0x55acec651d46 in _gameLoop /home/mfunk/src/BrogueCE/src/platform/sdl2-platform.c:367:5
    #7 0x55acec64e81e in main /home/mfunk/src/BrogueCE/src/platform/main.c:223:5
    #8 0x7f9ed44cc022 in __libc_start_main (/usr/lib/libc.so.6+0x27022)
    #9 0x55acec40752d in _start (/home/mfunk/src/BrogueCE/bin/brogue+0x1ef52d)

src/brogue/Monsters.c:2022:34: runtime error: index -1 out of bounds for type 'const short [8][2]'
    #0 0x55acec595cac in pathTowardCreature /home/mfunk/src/BrogueCE/src/brogue/Monsters.c:2022:34
    #1 0x55acec5afd1a in monstersTurn /home/mfunk/src/BrogueCE/src/brogue/Monsters.c:3351:17
    #2 0x55acec64955e in playerTurnEnded /home/mfunk/src/BrogueCE/src/brogue/Time.c:2410:25
    #3 0x55acec5c1926 in playerMoves /home/mfunk/src/BrogueCE/src/brogue/Movement.c
    #4 0x55acec4e37b6 in executeKeystroke /home/mfunk/src/BrogueCE/src/brogue/IO.c:2592:13
    #5 0x55acec561241 in mainBrogueJunction /home/mfunk/src/BrogueCE/src/brogue/MainMenu.c:852:25
    #6 0x55acec651d46 in _gameLoop /home/mfunk/src/BrogueCE/src/platform/sdl2-platform.c:367:5
    #7 0x55acec64e81e in main /home/mfunk/src/BrogueCE/src/platform/main.c:223:5
    #8 0x7f9ed44cc022 in __libc_start_main (/usr/lib/libc.so.6+0x27022)
    #9 0x55acec40752d in _start (/home/mfunk/src/BrogueCE/bin/brogue+0x1ef52d)

this suggests that dir is -1 in the following snippet:

    dir = nextStep(target->mapToMe, monst->xLoc, monst->yLoc, monst, true);
    targetLoc[0] = monst->xLoc + nbDirs[dir][0];
    targetLoc[1] = monst->yLoc + nbDirs[dir][1];

The errors reliably occur for me in this zipped recording at turn 686 with BrogueCE a53673d compiled with clang 9.
I am not really familiar with the codebase and cannot tell if this results in an actual observable bug or how to fix this in a good way. Feel free to close this issue if this is something that can be ignored.

[tmewett]

Thanks for the report. On what turn do you get these errors? And do they cause an out-of-sync error? I get an out-of-sync error on turn 686, does that seem right?

[krypt-n]

Yeah, the errors happen at turn 686, however I do not get an out-of-sync error.

[kz-dev]

I also have a out-of-sync at turn 686 when view your recording. You press "j" to go in water. Can we find seed in the recording file ? Or have you the seed ?

[krypt-n]

The seed is 232800572

[tmewett]

Ok! Looks like this is an out-of-sync bug. Good find, now we need to work out the cause.

[krypt-n]

I found another recording with this issue at turn 790, if that helps.

[tmewett]

I've found the cause of this issue.

If you go to turn 686 on your first recording, there are two small pools, each containing an eel. By some strange dungeon generation (bug?), those two eels are actually part of the same horde: one is a follower of the other. So the follower, being more than 2 cells away from its leader (condition in monstersTurn at Monsters.c:3350), tries to path towards the other eel with pathTowardCreature. However, there is no traversable path to follow - so nextStep returns -1, which isn't checked, and hence invalid access occurs.

This is a really good find, thanks for the report!

[flend]

Amazing work guys!