Pages: [1]   Go Down
 Author Topic: LOL shield maze game  (Read 623 times) 0 Members and 1 Guest are viewing this topic.
0
Offline
Newbie
Karma: 0
Posts: 13
Any problem has n+1 solutions
 « on: December 01, 2012, 03:06:59 pm » Bigger Smaller Reset

Here ia a nice game made for the LOL shield. It is part of a project to stimulate kids to play around with electronics and arduino. The rest of the project will be post on my blog:www.jelbert.nl as soon as it is ready.
It creates a maze (can be very large like 75x50). Then displays the part that will fit on the shield for 5 seconds and then let you walk the maze with only your field of view.
It uses an arduino mega 1280.

Ok the code is too much for this forum. In that case you can find it here http://www.jelbert.nl/?p=429
 Logged

Offline
Edison Member
Karma: 4
Posts: 1129
If you're not living on the Edge, you're taking up too much space!
 « Reply #1 on: December 01, 2012, 10:32:06 pm » Bigger Smaller Reset

I clicked your link but I didn't have much time to study the code yet.  How does it make a maze with only one possible solution?  Will it always be difficult, or sometimes trivial to solve?  Do you have to generate the maze manually?
 Logged

If you fall... I'll be there for you!
-Floor

Skype Brighteyes3333
(262) 696-9619

0
Offline
Newbie
Karma: 0
Posts: 13
Any problem has n+1 solutions
 « Reply #2 on: December 02, 2012, 05:18:49 am » Bigger Smaller Reset

The maze is created in a boolean array.
The array is first filled with walls '0'.
Then starting at 0,0 a routine walks at ranom through the maze.
It only walks here were no walkway are already and will not connect walk ways.
Then when in reaches an end and can go no further the routine starts again at 0,1 and tries to find a place from the walkway where the walkway can go without connecting roads.
This will create a maze with only one solution.

If the maze becomes huge like 50x50 or bigger, there are places in the maze where walkways still could be made and are not filled up. Solving a maze like that with only a viewport of 12 steps max. and rembering where you have been is not very likely so I did not solve that part yet.

Then in the end I have a routine scanning the 4x4 squeares in the lower right corner for walkway. The one closest to the higest coordinate (19,19) will be set as the exit of the maze. Once you reach that point the game will restart.

The game is mostly difficult to solve even if you know how it has been programmed.

Enhancements I want to make are playing a tune and an animation at the end of the game and increase level by making the maze bigger.

To make maze bigger the array will need to be bigger. But if the game is going to be part of a toolset for kids to play with (including the games that come with the lib) it could be handy to be able to release the memory occupied by the array. Is there a way to do that within the arduino?
 Logged

Offline
Edison Member
Karma: 4
Posts: 1129
If you're not living on the Edge, you're taking up too much space!
 « Reply #3 on: December 02, 2012, 09:48:21 am » Bigger Smaller Reset

Wonderful code!  I haven't tested it yet but I'm impressed.  I was obsessed with mazes when I was 8 for years.  I'd stick a fork in you if I could.  Well done.
 Logged

If you fall... I'll be there for you!
-Floor

Skype Brighteyes3333
(262) 696-9619

0
Offline
Newbie
Karma: 0
Posts: 13
Any problem has n+1 solutions
 « Reply #4 on: December 02, 2012, 12:19:26 pm » Bigger Smaller Reset

Thanks!
The code on my blog is displayed funny, or not realy funny since half is missing.
I included the maze.ino in this post so people willnot have to cut and paste funny code.
 Logged

0
Offline
Newbie
Karma: 0
Posts: 13
Any problem has n+1 solutions
 « Reply #5 on: December 03, 2012, 08:21:11 pm » Bigger Smaller Reset

Ok it is ready now. uses game levels starting at 10x10 fields and ending at 60x60 fields.

part1
Code:
/* maze builder
create a maze in a bolean array
Display the maze on the LOL shield
use the keys defined to move around the maze
Cheat sheet is displayed on serial port

This is free software; you can redistribute it and/or
modify it under the terms of the GNU Version 3 General Public
or (at your option) any later version.

Written by Jelbert Holtrop http://jelbert.nl
dec-2012

*/
#include <Charliplexing.h>
#include "Myfont.h"
#include "Arduino.h"

#define P(name)   static const prog_uchar name[] PROGMEM

#define xgridMax 60
#define ygridMax 60
#define xMazeDisplay 10
#define yMazeDisplay 5
#define dim1 5  //dim all so you dont get blind from playing this game all day ;-)
#define dim2 5  //for each distance you can set a dim so the farr walles are less bright
#define dim3 5

#define upKey 36
#define rightKey 38
#define downKey 40
#define leftKey 42

bool maze [xgridMax][ygridMax];
unsigned char mazeEndX,mazeEndY;
unsigned char xgrid = 10;
unsigned char ygrid = 10;

void setup()
{

LedSign::Init(GRAYSCALE);            //Initilizes the LoL Shield

pinMode(upKey, INPUT); //set key inputs
pinMode(rightKey, INPUT);
pinMode(downKey, INPUT);
pinMode(leftKey, INPUT);
digitalWrite(upKey,HIGH); //make pullup
digitalWrite(rightKey,HIGH);
digitalWrite(downKey,HIGH);
digitalWrite(leftKey,HIGH);
Serial.begin(9600);
for(int x=0; x< xgrid; x++) //empty maze
{
for(int y=0; y< ygrid; y++)
maze[x][y]=0;
}

Serial.println("strart run");
}

void loop()
{
int x,y;
for (char mazelevel=1;mazelevel<12;mazelevel++)
{
x=0;
y=0;
mazeLevel(mazelevel);
emptyMaze();
buildMaze();

LedSign::Clear();
LedSign::Clear();  //in the mega some pixels keep light. Clearing twice in atempt to fix this.
//testMaze();
displayMaze();
printMaze(); //the cheatsheet
delay(5000);
LedSign::Clear();
LedSign::Clear();
displayMazeSpot(x,y);

while(1)
{
if(moveMaze(x,y, 500)==1)
{ //if won do something nice, restart game
break;
}
LedSign::Set(xMazeDisplay,yMazeDisplay,7);
delay(100);
LedSign::Set(xMazeDisplay,yMazeDisplay,0);
delay(100);
};
}
}

void emptyMaze()
{

for(int x=0; x< xgridMax; x++) //empty maze
{
for(int y=0; y< ygridMax; y++)
maze[x][y]=0;
}
}

void printMaze()
{
Serial.print(xgrid,DEC);
Serial.print(',');
Serial.println(ygrid,DEC);

for(int y=0; y< ygrid; y++) //print maze
{
for(int x=0; x< xgrid; x++)
{
if(maze[x][y]==0)
Serial.print('X');
else
Serial.print(' ');
}
Serial.println('|');

}

Serial.print("Maze End =");
Serial.print(mazeEndX,DEC);
Serial.print(',');
Serial.println(mazeEndY,DEC);
Serial.println(freeRam());

}

void mazeLevel(char level)
{
//avoid at all costs to use string functions due to weird bugs
//save ram space put strings in flash.
//say something nice with each level. Would like to make sound too but that messes up te display timer
P(Level1Maze)="Speel nivo 1 ... 10x10 velden"; //29
P(Level2Maze)="Speel nivo 2 ... 15x15 velden"; //29
P(Level3Maze)="Speel nivo 3 ... 20x20 velden Joepiii!!"; //39
P(Level4Maze)="Speel nivo 4 ... 25x25 velden Goedzo!!!"; //39
P(Level5Maze)="Speel nivo 5 ... 30x30 velden Een echte ster!!"; //46
P(Level6Maze)="Speel nivo 6 ... 35x35 velden En nu voor het kampioenschap"; //58
P(Level7Maze)="Speel nivo 7 ... 40x40 velden beste score to nu toe!!"; //53
P(Level8Maze)="Speel nivo 8 ... 45x45 velden ONGELOFELIJK!!!"; //45
P(Level9Maze)="Speel nivo 9 Wauw !!! ... 50x50 velden"; //37
P(Level10Maze)="Speel nivo 10 Helemaal geweldig... 55x55 velden"; //47
P(Level11Maze)="Speel nivo 11 toppie toptop ... 60x60 velden"; //44

switch (level)
{
case 1:
Pbanner(29, Level1Maze);
xgrid=10;
ygrid=10;
break;
case 2:
Pbanner(29, Level2Maze);
xgrid=15;
ygrid=15;

break;
case 3:
Pbanner(39, Level3Maze);
xgrid=20;
ygrid=20;

break;
case 4:
Pbanner(39, Level4Maze);
xgrid=25;
ygrid=25;

break;
case 5:
Pbanner(46, Level5Maze);
xgrid=30;
ygrid=30;

break;
case 6:
Pbanner(58, Level6Maze);
xgrid=35;
ygrid=35;

break;
case 7:
Pbanner(53, Level7Maze);
xgrid=40;
ygrid=40;
break;
case 8:
Pbanner(45, Level8Maze);
xgrid=45;
ygrid=45;
break;
case 9:
Pbanner(37, Level9Maze);
xgrid=50;
ygrid=50;
break;
case 10:
Pbanner(47, Level10Maze);
xgrid=55;
ygrid=55;
break;
case 11:
Pbanner(44, Level11Maze);
xgrid=60;
ygrid=60;
break;

}
}

void Pbanner(unsigned char len, const prog_uchar *text)
{//modified from the LOL lib
char c;
int xoff=14;/* setmx offset to the right end of the screen*/
for(int i=0; i<len*5 +52; i++){ /*scrolling loop*/
for(int j=0; j<len; j++){ /*loop over all of the chars in the text*/
Myfont::Draw(xoff + j*6, c); /* call the draw font function*/
}
xoff--; /* decrement x offset*/
delay(70); /*scrolling speed increments if delay goes down*/
LedSign::Clear(); /*empty the screen */
}

}
int freeRam () {
extern int __heap_start, *__brkval;
int v;
return (int) &v - (__brkval == 0 ? (int) &__heap_start : (int) __brkval);
}

/*
void testMaze()
{
maze[0][0]=1;
for( int x=0;x<6;x++)
maze[x][1]=1;

for (int y=2;y<6;y++)
maze[5][y]=1;

for( int x=2;x<6;x++)
maze[x][5]=1;

for (int y=3;y<6;y++)
maze[2][y]=1;

maze[3][3]=1;

}*/

bool moveMaze(int &x, int &y, int timeout)
{
unsigned long t;

t=timeout+millis(); //get exit time
while(t>millis())
{
{//do move up
if(y>0)
{
if(maze[x][y-1]==1)
y--;

Serial.print("x=");
Serial.print(x,DEC);
Serial.print(" y=");
Serial.println(y,DEC);
break;
}
}
{//do move right
if(x<xgrid)
{
if(maze[x+1][y]==1)
x++;

Serial.print("x=");
Serial.print(x,DEC);
Serial.print(" y=");
Serial.println(y,DEC);
break;
}
}
{//do move down
if(y<ygrid)
{
if(maze[x][y+1]==1)
y++;
Serial.print("x=");
Serial.print(x,DEC);
Serial.print(" y=");
Serial.println(y,DEC);
break;
}
}
{//do move left
if(x>0)
{
if(maze[x-1][y]==1)
x--;
Serial.print("x=");
Serial.print(x,DEC);
Serial.print(" y=");
Serial.println(y,DEC);
break;
}
}

};
//eraseMazeSpot();
LedSign::Clear();
displayMazeSpot(x,y);
if(x==mazeEndX && y==mazeEndY)
return 1;
else
return 0;

}

void eraseMazeSpot()
{
int xe,xf,ye,yf;
xe=xMazeDisplay-3;
xf=xMazeDisplay+3;
ye=yMazeDisplay-3;
yf=yMazeDisplay+3;
if (xe<0)
xe=0;
if(xf>xgrid)
xf=xgrid;
if (ye<0)
ye=0;
if(yf>ygrid)
yf=ygrid;
for(int x=xe;x<xf+1;x++)
{
for(int y=ye;y<yf+1;y++)
{
LedSign::Set(x,y,0);
}
}
}

 Logged

0
Offline
Newbie
Karma: 0
Posts: 13
Any problem has n+1 solutions
 « Reply #6 on: December 03, 2012, 08:22:17 pm » Bigger Smaller Reset

part 2:
Code:

void displayMazeSpot(int x, int y)
{
//display what can be seen from this spot in the maze
//the 8 surounding leds can always be seen
setDot1(x,y, -1, -1, dim1);
setDot1(x,y,  0, -1, dim1);
setDot1(x,y,  1, -1, dim1);
setDot1(x,y, -1,  0, dim1);
setDot1(x,y,  1,  0, dim1);
setDot1(x,y, -1,  1, dim1);
setDot1(x,y,  0,  1, dim1);
setDot1(x,y,  1,  1, dim1);
if(getMaze(x,y-1)==1)
{
setDot1(x,y,  0,  -2, dim2);
setDot1(x,y, -1,  -2, dim2);
setDot1(x,y,  1,  -2, dim2);
if(getMaze(x,y-2)==1)
{
setDot1(x,y,  0,  -3, dim3);
setDot1(x,y, -1,  -3, dim3);
setDot1(x,y,  1,  -3, dim3);
}
}
if(getMaze(x,y+1)==1)
{
setDot1(x,y,  0,  2, dim2);
setDot1(x,y, -1,  2, dim2);
setDot1(x,y,  1,  2, dim2);
if(getMaze(x,y+2)==1)
{
setDot1(x,y,  0,  3, dim3);
setDot1(x,y, -1,  3, dim3);
setDot1(x,y,  1,  3, dim3);
}
}
if(getMaze(x-1,y)==1)
{
setDot1(x,y, -2,   0, dim2);
setDot1(x,y, -2,  -1, dim2);
setDot1(x,y, -2,   1, dim2);
if(getMaze(x-2,y)==1)
{
setDot1(x,y, -3,   0, dim3);
setDot1(x,y, -3,  -1, dim3);
setDot1(x,y, -3,   1, dim3);
}
}
if(getMaze(x+1,y)==1)
{
setDot1(x,y, 2,   0, dim2);
setDot1(x,y, 2,  -1, dim2);
setDot1(x,y, 2,   1, dim2);
if(getMaze(x+2,y)==1)
{
setDot1(x,y, 3,   0, dim3);
setDot1(x,y, 3,  -1, dim3);
setDot1(x,y, 3,   1, dim3);
}
}
}

void setDot(int x, int y, int dim)
{

LedSign::Set(x,y,(1-maze[x][y])*dim);
}

void setDot1(int x, int y, int xo, int yo, int dim)
{
//include bounds detection & dispay to spot
x=x+xo;
y=y+yo;
if(x>=0 && x<=xgrid && y>=0 && y<=ygrid)
LedSign::Set(xMazeDisplay+xo,yMazeDisplay+yo,(1-maze[x][y])*dim);
}

bool getMaze(int x, int y)
{
if(x>=0 && x<=xgrid && y>=0 && y<=ygrid)
return maze[x][y];
else
return 0; //if outside maze it is a wall
}

void displayMaze()
{
int x,y;
x=xgrid;
if(xgrid>14)
x=14;
y=ygrid;
if(ygrid>9)
y=9;
for(int xx=0; xx< x; xx++) //print maze
{
for(int yy=0; yy< y; yy++)
{
LedSign::Set(xx,yy,(1-maze[xx][yy])*dim1);
}
}
}

void buildMaze()
{
/*
in what direction to go?
1=5= right x+1
2=6= down Y+1
3=7= left x-1
4= up y-1
direction = old direction + rnd(3)
Is the new direction correct?
coordinate assignments for up move see table below.
the E & F fields could be ommited but the maze would then seem to have many diagonal moves.
0 E D F 0
0 A B C 0
0 0 Q 0 0
0 0 0 0 0
0 0 0 0 0
From Q A is not used or the limit of the board, I not used K not used. then A is next Q
Same goes for the others.
All directions are filled?
Test all locations until a spot is found that is used Q where A is not used or the limit of the board, I not used K not used. then A is next Q
Same goes for the others.
Relative positions to check from Q in relation to grid:
UP      Right      Down      Left
A(-1,-1)  (1,-1)    (-1,1)    (-1,-1)
B(0 ,-1)  (1, 0)    ( 0,1)    (-1, 0)
C(1 ,-1)  (1, 1)    ( 1,1)    (-1, 1)
D(0 ,-2)  (2, 0)    ( 0,2)    (-2, 1)
E(-1,-2)  (2,-1)    ( 1,2)    (-2, 1)
F( 1,-2)  (2, 1)    (-1,2)    (-2,-1)

First choose rnd(direction) then test if direcrion is ok
Any used spot is 1 so 1 is road 0 is wall

*/
char dir, olddir=1;
int x=0,y=0;
//char runs=0;
char tries=0;
// for(int runs=0;runs<5;runs++)
maze[0][0]=1; //start position
for(int x1=0; x1< xgrid; x1++) //find empty sports and build maze
{
for(int y1=0; y1< ygrid; y1++)
{// try to build maze from this spot

//       Serial.print("X=");
//       Serial.print(x,DEC);
//       Serial.print(" Y=");
//       Serial.print(y,DEC);
//       Serial.print(" tries=");
//       Serial.println(tries,DEC);
tries=0;
x=x1;
y=y1;
if(maze[x][y]==1)
{
while(tries<5) //try this until solution found
{
dir=olddir+random(3);
//       Serial.print(" Dir=");
//       Serial.println(dir,DEC);
switch (dir)
{
case 1:
case 5:
//right
olddir=1;
tries++;
if(rightMove(x,y))
{
x++;
maze[x][y]=1;
tries=0;
}
break;
case 2:
case 6:
//down
olddir=2;
tries++;
if(downMove(x,y))
{
y++;
maze[x][y]=1;
tries=0;
}
break;
case 3:
case 7:
//left
olddir=3;
tries++;
if(leftMove(x,y))
{
x--;
maze[x][y]=1;
tries=0;
}
break;
case 4:
//up
tries=0;
if(upMove(x,y))
{
y--;
maze[x][y]=1;
tries=0;
}
break;

}

}

}
}
}
findMazeEnd();
}

bool rightMove(int x,int y)
{
char ax, bx, cx, dx, ex, fx, ay, by, cy, dy, ey ,fy;
ax=x+1;
bx=x+1;
cx=x+1;
dx=x+2;
ex=x+2;
fx=x+2;
ay=y-1;
by=y;
cy=y+1;
dy=y;
ey=y-1;
fy=y+1;
if(ax == xgrid) //test grid limits
return 0; //right move not possible
if (ay < 0)
{
ay=0;
ey=0;
}
if (cy == ygrid) //test grid limits
{
cy=y;
fy=y;
}
if (dx >= xgrid)
{
dx=cx;
ex=cx;
fx=cx;
}
if(maze[ax][ay]==0 && maze[bx][by]==0 && maze[cx][cy]==0 && maze[dx][dy]==0 && maze[ex][ey]==0 && maze[fx][fy]==0)
{
x++;
maze[x][y]=1;
return 1;
}
return 0;

}

bool downMove(int x, int y)
{
char ax, bx, cx, dx, ex, fx, ay, by, cy, dy, ey ,fy;
ax=x-1;
bx=x;
cx=x+1;
dx=x;
ex=x+1;
fx=x-1;
ay=y+1;
by=y+1;
cy=y+1;
dy=y+2;
ey=y+2;
fy=y+2;
if(ay == ygrid) //test grid limits
return 0;  //down is not possible
if (ax<0)
{
ax=0;
fx=0;
}
if (cx=xgrid)
{
cx=x;
ex=x;
}
if(dy >= ygrid)
{
dy=cy;
ey=cy;
fy=cy;
}
if(maze[ax][ay]==0 && maze[bx][by]==0 && maze[cx][cy]==0 && maze[dx][dy]==0 && maze[ex][ey]==0 && maze[fx][fy]==0)
{
y++;
maze[x][y]=1;
return 1;
}
return 0;
}

bool leftMove(int x, int y)
{
char ax, bx, cx, dx, ex, fx, ay, by, cy, dy, ey ,fy;

ax=x-1;
bx=x-1;
cx=x-1;
dx=x-2;
ex=x-2;
fx=x-2;
ay=y-1;
by=y;
cy=y+1;
dy=y;
ey=y+1;
fy=y-1;
if(ax<0)
return 0;
if(ay<0)
{
ay=0;
fy=0;
}
if(cy==ygrid)
{
cy=y;
ey=y;
}
if(dx <= 0)
{
dx=0;
ex=0;
fx=0;
}
if(maze[ax][ay]==0 && maze[bx][by]==0 && maze[cx][cy]==0 && maze[dx][dy]==0 && maze[ex][ey]==0 && maze[fx][fy]==0)
{
x--;
maze[x][y]=1;
return 1;
}
return 0;

}

bool upMove(int x, int y)
{
char ax, bx, cx, dx, ex, fx, ay, by, cy, dy, ey ,fy;
ax=x-1;
bx=x;
cx=x+1;
dx=x;
ex=x-1;
fx=x+1;
ay=y-1;
by=y-1;
cy=y-1;
dy=y-2;
ey=y-2;
fy=y-2;
if(ay<0)
return 0;
if(ax<0)
{
ax=0;
ex=0;
}
if(cx==xgrid)
{
cx=x;
fx=x;
}
if (dy <= 0)
{
dy=0;
ey=0;
fy=0;
}
if(maze[ax][ay]==0 && maze[bx][by]==0 && maze[cx][cy]==0 && maze[dx][dy]==0 && maze[ex][ey]==0 && maze[fx][fy]==0)
{
y--;
maze[x][y]=1;
return 1;
}
return 0;
}

void findMazeEnd()
{
// the maze will fill completely so only look in the lower right corner
for(int y=ygrid-1; y>(ygrid-4); y--)
{
for(int x=xgrid-1; x>(xgrid-4); x--)
{
if(maze[x][y]==1)
{
mazeEndX=x;
mazeEndY=y;
return;
}
}
}
}

 Logged

 Pages: [1]   Go Up