I am writing a program to solve Sokoban levels – because why not. The initial trigger for writing the program was to show a colleague how a program can be written using the MVC pattern. From there, it evolved.
The good: for some warehouses, the solver finds the proper solutions. I know because I created some simplified warehouses for verification and debugging purposes, with obvious solutions.
The bad: it does not work correctly.
The ugly: I do not understand why, and therefore I cannot fix it.
NOTE: If the program cannot solve the level for some reason, it is acceptable. But the behaviors presented below are definitely unacceptable.
The simplest Sokoban which is not already solved from the start: the warehouse keeper, the box and then the destination place. The only move possible, solves the game. Works as expected.
The next verifies that recursions work because they are good, not because they are special cases. Also works fine, it finds both solutions.
Another one with a "funny ventilator" shape, also finding all solutions correctly.
But if I try to solve something more realistic (e.g., the first Sokoban level, I tried also microcosmos.5 with same results), things go wrong. The Sokoban starts to walk on the walls, like a Cyber-Hympty-Dumpty (graphically visible below), and even goes "severely" outside the walls like a very naughty ghost not willing to stay constrained in the cemetery (see the error messages; 0 < row < 11, column should not be less than 1, let alone negative).
I already reviewed the code several time and removed all bugs I found. I have lots of boundary checks. I enabled all compiler warnings.
I increased the stack and heap 100 fold (or more?).
And the command line generated by Codeblocks:
x86_64-w64-mingw32-gcc.exe -Wshadow -Winit-self -Wredundant-decls -Wcast-align -Wundef -Wfloat-equal -Winline -Wunreachable-code -Wmissing-declarations -Wmissing-include-dirs -Wswitch-enum -Wswitch-default -Wmain -pedantic -Wextra -Wall -std=c17 -m64 -pedantic -Wextra -Wall -std=c17 -g -pedantic -Wextra -Wall -std=c17 -m64 -I..\..\..\cb_20_03\MinGW\opt\include -c Z:\_progs\_progsData\cb\sokoban\main.c -o obj\Debug\main.o
x86_64-w64-mingw32-gcc.exe -L……\cb_20_03\MinGW\opt\lib -o bin\Debug\sokoban.exe obj\Debug\main.o -m64 -Wl,–stack,819430400 -Wl,–heap,819430400 -fstack-protector-all -m64 ……\cb_20_03\MinGW\opt\lib\libncursesw.a
The only explanations that I find for the things going wrong are:
- some reading / writing beyond the array or malloc()-ated boundaries;
- stack insufficient;
- heap insufficient;
But I already increased the stack and the heap a lot (I guess), and the behavior does not change.
The needs
I need some debugging help (in the debugging build, of course) for the following:
- to "automatically" detect memory accesses in the wrong places;
- stack insufficient;
- heap insufficient;
- API to know the size of the remaining stack;
- API to know the size of the remaining heap;
- others.
I use:
- Codeblocks 20.03 under MS Windows 10 for writing the code and debugging
- mingw (the one delivered together with Codeblocks)
- alternatively, mingw64 – with not much different behavior
I have zero warnings / errors after a full rebuild. CppCheck also does not highlight any wrongdoing (most messages are about missing headers and reducing the scope of some variables).
I cannot just go through the execution step by step, because the wrong behavior appears quite late – I would lose all focus before I would get to the point to notice the actual problem.
I do not post the source code here, because it has ~1000 lines. This question is not really about the code itself, but how to find the problem.
Any help is more than welcome.
You need to sign in to view this answers
Leave feedback about this