FS#9191 - Revamp of maze plugin code (apps/plugins/maze.c)

Attached to Project: Rockbox
Opened by William Poetra Yoga Hadisoeseno (wpyh) - Sunday, 13 July 2008, 19:19 GMT
Last edited by Jonathan Gordon (jdgordon) - Tuesday, 15 July 2008, 13:49 GMT
Task Type Patches
Category Games
Status Closed
Assigned To No-one
Operating System All players
Severity Low
Priority Normal
Reported Version Daily build (which?)
Due in Version Undecided
Due Date Undecided
Percent Complete 100%
Votes 0
Private No


I've revamped the code in apps/plugins/maze.c while fixing the bug in  FS#9184 . Here are the main changes:

1. Whitespace changes.

2. Code cleanups.

3. Comments for non-trivial code blocks.

4. Make all functions static.

5. Reorder and regroup several functions.

6. Use border-detection macros instead of border property bits, use 8 bit entities for each cell.

7. Only solve the maze the first time maze_solve() is called.

8. Add and use maze.show_path to control whether the solution is displayed.

9. Modify the path bits only in maze_solve().

10. Modify the algorithm in maze_solve() to make it clearer.

11. Link together the solution instead of showing discrete blocks.

12. Rewrite maze_pick_random_neighbour_cell_with_walls(), and remove coord_stack_count() and coord_stack_get().

13. Rewrite the coordinate stack operations, use arrays of x and y coordinates.

14. Remove bug workaround with rb->yield() when quitting.

This fixes  FS#9184 , so if this patch is accepted, that task can also be closed.
This task depends upon

Closed by  Jonathan Gordon (jdgordon)
Tuesday, 15 July 2008, 13:49 GMT
Reason for closing:  Accepted
Comment by x (vmh) - Monday, 14 July 2008, 16:17 GMT
Your patch fixes  FS#9184  on my E200. What was the cause for the crash?
Comment by William Poetra Yoga Hadisoeseno (wpyh) - Monday, 14 July 2008, 18:17 GMT
Well, I'm not really sure how it works, but the crash was caused by some stack overflow.

The quick fix was to change:

struct coord_stack
int stp;


struct coord_stack
unsigned short data[MAZE_WIDTH*MAZE_HEIGHT];
int stp;

But as you can see,
1. That "fix" was too simplistic and didn't take into account other factors.
2. The data (array) inside struct coord_stack and struct_maze are similar only because of a coincidence.
3. I got itchy and started making changes here and there.

I've played with it and didn't find any problems. Solving the maze takes some time, and I hope that can be optimized, but let's save it for later. I'm hoping this patch gets accepted first :)
Comment by x (vmh) - Monday, 14 July 2008, 19:50 GMT
Thank you for the explanation. I think I see the problem.
The parameters x and y for push and pop are integers, but only the lower 8 bits from x and y are used.
When x or y exceeds 255 or negative, the value on the stack will be wrong.
It's funny that if you change the stack to 'unsigned short' will work.
I would say the correct fix for the old code would be to leave the stack as integer but change the parameters x and y for push and pop to unsigned short.

I see in your new version the parameters for the data to push and pop from stack are still integer while the stack is expecting unsigned short.
I would change it if I were you.
Comment by x (vmh) - Monday, 14 July 2008, 20:19 GMT
Here is a patch for the original maze code. I cleared the higher 8 bits from y which can corrupt the stack and it works on my player.
Comment by William Poetra Yoga Hadisoeseno (wpyh) - Tuesday, 15 July 2008, 03:54 GMT
That is even stranger than the original problem. coord_stack_push is called with x and y coordinates, which can never be negative or more than 255. Actually the largest maze we have is 32x24 (and this will be the largest for quite a long time).

Therefore I think the problem lies with some code that calls coord_stack_push with invalid coordinates. By clearing the higher bits from y, we are effectively hiding the problem. Please track down the caller :)

Meanwhile, my patch changes the function to:

static void coord_stack_push(struct coord_stack* stack, int x, int y)
stack->x[stack->stp] = x;
stack->y[stack->stp] = y;

The stack is implemented by two uint8_t arrays, which means that x and y are cast to uint8_t. This means that if a caller calls coord_stack_push with the wrong values, it will still behave erratically. However, we cannot solve the problem inside this function. We have to track down the caller.

Since I've rewritten / revamped most of the functions, the problem may have been fixed by me, or hidden somewhere. I hope that you will test my patch, and see whether it works correctly, especially for showing the path (the solution, see maze_draw()) -- I've linked the cells in the path, as opposed to just highlighting every cell in the path.
Comment by William Poetra Yoga Hadisoeseno (wpyh) - Tuesday, 15 July 2008, 05:04 GMT
This is a newer version.

15. Moved "#include pluginlib_actions.h" and plugin_contexts into one #ifdef.