Anything Forums

Code: Select all

/*----------------------------------------------------------------------+
|       Title:  mazeWalker.c                                            |
|               Reinforcement learning used to navigate through a maze  |
|                                                                       |
|       Authors: Mark Hokanson                                          |
|                Matt Waxman                                            |
|                Dan Prantl                                             |
|                Clark University                                       |
|                Worcester, MA 01610-1477                               |
|                U.S.A.                                                 |
|                                                                       |
|       Date:   April 1998.                                             |
|       Time Stamp:  <98/04/24 19:38:48 waxman>                         |
+----------------------------------------------------------------------*/

#include <stdio.h>
#include "RoboSim.h"
#include "SimDisp.h"
#include <time.h>
#include <unistd.h>
#include <math.h>

#define WALL_LENGTH 1000
#define PIXEL_SIZE 100
#define ROBOT_SIZE 80
#define DISPLAY_CORRECTION 80
#define SUCCESS 1
#define FAIL 0
#define UP 2
#define DOWN 0
#define RIGHT 1
#define LEFT 3
#define GAMMA 0.9
#define GOAL_X 10 /* Goal State Coords */
#define GOAL_Y 7
#define WALL -1
#define RANDOM_WALKS 25
#define GOAL_AMOUNT 1000
#define WALL_WIDTH 0.3*PIXEL_SIZE

/* Function prototypes */
int  moveUp(void);
int  moveDown(void);
int  moveLeft(void);
int  moveRight(void);
void randomMove(void);
void selectiveMove(void);
void q_function(void);
void printGrid(void);
void createWalls(World *w);
void add_wall(World *w, int from_x, int from_y, int to_x, int to_y);
void test(World *w);

/* Global Variables */
Point p;
SimDisp *sd;
World *w;
Robot *r;
int x,y;
int grid[WALL_LENGTH/PIXEL_SIZE][WALL_LENGTH/PIXEL_SIZE];

void 
main(void)
{
  int i,j, coordx=1, coordy=1;

  w = makeWorld(WALL_LENGTH,WALL_LENGTH);
  sd = makeSimDisp(w, 1, "black", "purple", "red");
  r = makeRobot(ROBOT_SIZE,ROBOT_SIZE);  
  p.x = (PIXEL_SIZE*0.1);  p.y = (PIXEL_SIZE*0.1)+DISPLAY_CORRECTION;
  x=0; y=0;
  addRobot(w, r, p, 0);  
  drawWorld(sd);

  /* initialize grid to all 0's */
  for(i=0;i<WALL_LENGTH/PIXEL_SIZE;i++)
    {
      for(j=0;j<WALL_LENGTH/PIXEL_SIZE;j++)
	grid[i][j]=0;
    }
  
  /* set goal state */
  grid[GOAL_X-1][GOAL_Y-1]=GOAL_AMOUNT;
  
  createWalls(w);
  drawWorld(sd);
  
  q_function();
  
  /* move back to start position (top left) */
  p.x = (PIXEL_SIZE*0.1);  p.y = (PIXEL_SIZE*0.1)+DISPLAY_CORRECTION;
  x=0; y=0;

  drawWorld(sd);
  addRobot(w, r, p, 0);  
  drawWorld(sd);
  while(x!=(GOAL_X-1) || y!=(GOAL_Y-1))
    {
      selectiveMove();
      drawWorld(sd);
      sleep(1);
    }
}

int
moveUp()
{
  p.y = p.y-PIXEL_SIZE;
  if(p.y<0 || grid[x][y-1]==WALL) 
    {
      p.y=p.y+PIXEL_SIZE;
      return FAIL;
    }
  else 
    {
      addRobot(w, r, p, 0);  
      y--;
      return SUCCESS;
    }
}

int
moveDown()
{
  p.y = p.y+PIXEL_SIZE;
  if(p.y>WALL_LENGTH || grid[x][y+1]==WALL) 
    {
      p.y = p.y-PIXEL_SIZE;
      return FAIL;
    }
  else 
    {
      addRobot(w, r, p, 0);  
      y++;
      return SUCCESS;
    }
}

int
moveLeft()
{
  p.x = p.x-PIXEL_SIZE;
  if(p.x<0 || grid[x-1][y]==WALL) 
    {
      p.x = p.x+PIXEL_SIZE;
      return FAIL;
    }
  else 
    {
      addRobot(w, r, p, 0);  
      x--;
      return SUCCESS;
    }
}

int
moveRight()
{
  p.x = p.x+PIXEL_SIZE;
  if(p.x>WALL_LENGTH || grid[x+1][y]==WALL) 
    {
      p.x = p.x-PIXEL_SIZE;
      return FAIL;
    }
  else 
    {
      addRobot(w, r, p, 0);  
      x++;
      return SUCCESS;
    }
}

void 
randomMove(void)
{
  int i,temp;
  
  for(i=0;i<1;i++)
    {
      temp=rand()%4;
      switch (temp)
	{
	case DOWN:
	  if(!moveDown()) i--;
	  break;
	case RIGHT:
	  if(!moveRight()) i--;
	  break;
	case UP:
	  if(!moveUp()) i--;
	  break;
	case LEFT:
	  if(!moveLeft()) i--;
	  break;
	}
    }
}

void 
selectiveMove(void)
{
  int temp_value,move;
  
  /* NOTE: should be an && but for some reason the compiler thinks of them opposite */
  temp_value=0;
  if((y-1)>0)
    if(temp_value<grid[x][y-1])
      {
	temp_value=grid[x][y-1];
	move=UP;
      }
  if((x+1)<WALL_LENGTH/PIXEL_SIZE)
    if(temp_value<grid[x+1][y]) 
      {
	temp_value=grid[x+1][y];
	move=RIGHT;
      }
  if((y+1)<WALL_LENGTH/PIXEL_SIZE)
    if(temp_value<grid[x][y+1]) 
      {
	temp_value=grid[x][y+1];
	move=DOWN;
      }
  if((x-1)>0)
    if(temp_value<grid[x-1][y]) 
      {
	temp_value=grid[x-1][y];
	move=LEFT;
      }
  if(temp_value==0) 
    randomMove();
  else 
    {
      switch (move)
	{
	case DOWN:
	  if(moveDown()) ;
	  break;
	case RIGHT:
	  if(moveRight()) ;
	  break;
	case UP:
	  if(moveUp()) ;
	  break;
	case LEFT:
	  if(moveLeft()) ;
	  break;
	}
    }
}

void 
q_function(void)
{
  int temp_x,temp_y;
  int walks=0, i=0;
  while(walks<RANDOM_WALKS)
    {
      rewind(stderr);
      temp_x=x; temp_y=y;
      if(rand()%2==1) randomMove();
      else selectiveMove();
      /*      if(i++%100==1) 
	      drawWorld(sd); update display every 10 iterations */
      if(grid[temp_x][temp_y]<(grid[x][y]*GAMMA))
	grid[temp_x][temp_y]= GAMMA*grid[x][y];
      if(x==GOAL_X-1 && y==GOAL_Y-1) 
	{
	  walks++;
	  p.x = (PIXEL_SIZE*0.1);  p.y = (PIXEL_SIZE*0.1)+DISPLAY_CORRECTION;
	  x=0; y=0;
	  addRobot(w, r, p, 0);  
	  drawWorld(sd);
	}
    }
  printGrid();
}

void 
printGrid(void)
{
  int i,j;
  for(i=0;i<WALL_LENGTH/PIXEL_SIZE;i++)
    {
      for(j=0;j<WALL_LENGTH/PIXEL_SIZE;j++)
	fprintf(stderr,"%d	",grid[j][i]);
      fprintf(stderr,"
");
    }
}

/* set walls */
void 
createWalls(World *w)
{
  Point p1,p2;
  int i;

  grid[1][0]=WALL;
  grid[1][1]=WALL;
  grid[1][2]=WALL;
  grid[3][2]=WALL;
  grid[3][3]=WALL;
  grid[4][3]=WALL;
  grid[5][3]=WALL;
  grid[5][2]=WALL;
  grid[7][2]=WALL;
  grid[8][2]=WALL;
  grid[8][3]=WALL;
  grid[8][4]=WALL;
  grid[8][5]=WALL;
  grid[7][5]=WALL;
  grid[7][6]=WALL;
  grid[7][7]=WALL;
  grid[6][7]=WALL;
  grid[5][7]=WALL;
  grid[5][6]=WALL;
  grid[5][5]=WALL;
  grid[9][5]=WALL;
  grid[9][7]=WALL;
  grid[2][6]=WALL;
  grid[2][7]=WALL;
  grid[2][8]=WALL;
  grid[2][9]=WALL;
  grid[2][5]=WALL;
  grid[2][4]=WALL;
  grid[3][4]=WALL;
  
  
  add_wall(w,120,0,120,280);
  add_wall(w,320,220,320,420);
  add_wall(w,220,420,380,420);
  add_wall(w,520,220,520,320);
  add_wall(w,320,320,580,320);
  add_wall(w,720,220,820,220);
  add_wall(w,820,220,820,520);
  add_wall(w,720,520,1000,520);
  add_wall(w,720,520,720,720);
  add_wall(w,520,520,520,720);
  add_wall(w,520,720,780,720);
  add_wall(w,220,420,220,1000);
  add_wall(w,920,720,1000,720);
/*
  for(i=100;i<=900;i=i+100)
    {
      p1.x=i; p1.y=0;
      p2.x=i; p2.y=1000;
      addWall(w,p1,p2);
    }
  for(i=100;i<=900;i=i+100)
    {
      p1.x=0; p1.y=i;
      p2.x=1000; p2.y=i;
      addWall(w,p1,p2);
    }*/
}

void 
add_wall(World *w, int from_x, int from_y, int to_x, int to_y)
{
  Point p1, p2;
  int i;
  
  p1.x=from_x; p1.y=from_y;
  p2.x=to_x; p2.y=to_y;
  addWall(w,p1,p2);
  for(i=0;i<WALL_WIDTH;i++)
    {
      if(from_y==to_y) 
	{
	  p1.x=from_x; p1.y=from_y+i-1;
	  p2.x=to_x; p2.y=to_y+i-1;
	  addWall(w,p1,p2);
	  p1.x=from_x; p1.y=from_y+i+1;
	  p2.x=to_x; p2.y=to_y+1+i;
	  addWall(w,p1,p2);
	  from_y++;
	  to_y++;
	}
      else
	{
	  p1.x=from_x+i-1; p1.y=from_y;
	  p2.x=to_x+i-1; p2.y=to_y;
	  addWall(w,p1,p2);
	  p1.x=from_x+i+1; p1.y=from_y;
	  p2.x=to_x+1+i; p2.y=to_y;
	  addWall(w,p1,p2);
	  from_x++;
	  to_x++;
	}
    }
}

void test(World *w)
{
  Point p1,p2;
  int i;
  for(i=0;i==1000;i=i+100)
    {
      p1.x=i; p1.y=0;
      p2.x=i; p2.y=1000;
      addWall(w,p1,p2);
    }
  for(i=0;i==1000;i=i+100)
    {
      p1.x=0; p1.y=i;
      p2.x=0; p2.y=i;
      addWall(w,p1,p2);
    }
}

Code: Select all

#include<iostream>
#include<string>
#include<fstream>
#include<conio.h>

using namespace std;

class point2D
{
public:
    int x;
    int y;
    char dir; 
    
    point2D()
    {
    //default to 0,0 B (B for blank)
    x=0;
    y=0;
    dir='B';
    }
    
    point2D(int px,int py)
    {
    x=px;
    y=py;
    dir='S';
    }
    
    point2D(int px,int py,char pdir)
    {
    x=px;
    y=py;
    pdir=pdir;
    }
    
    bool operator==(point2D test)
    {
    return (test.x==x && test.y==y);        
    }
    
    bool operator!=(point2D test)
    {
    return !(test.x==x && test.y==y);        
    }

    
};//end point2D class


#include "stack.h"



class Map
{
private:
    int sizex;  //X max
    int sizey;  //Y max
    bool mapdata[16][16];  //the actual map
    char wall;      //ascii char for wall
    point2D ast;    //current position
    point2D start;  //start point
    point2D end;    //end point
    stack moves;    //each successful move is recorded to this stack (will be backwards)


public:
    
    Map()//default to #
    {
    wall='#';
    }
    
    Map(char pwall) //specify wall ascii code
    {   
    sizex=16;
    sizey=16;
    wall=pwall;   
    }
    
   bool LoadFile(string filename) //load map file into map table
   {
   ifstream fin(filename.c_str());
   
   if(!fin)return false;
   
   fin>>start.x>>start.y>>end.x>>end.y>>start.dir;
   
   ast=start;
   
   char tmp;
   
   for(int i=0;i<sizex;i++)
   {
        for(int ii=0;ii<sizey;ii++)
        {
        fin>>tmp;
        if(tmp=='0')mapdata[ii][i]=true;//passable
        else mapdata[ii][i]=false;      //impassable        
        }
   }
   
   
   fin.close();
   
   return true; 
   }
    
    
    
    void Display() //display map
    {
        for(int i=0;i<sizex;i++)
        {
            for(int ii=0;ii<sizey;ii++)
            {
            if (ast.x==ii && ast.y==i)cout<<"{}";    
            else if(end.x==ii && end.y==i)cout<<"Ex";    
            else if(!mapdata[ii][i])cout<<wall<<wall;
            else cout<<"  ";
            }
       
        cout<<"
";
        }    
        
     cout<<"Location: ("<<ast.x<<","<<ast.y<<") "<<ast.dir<<endl;    
    }
    
    
    
    bool Move(char dir) //attempt a move, in specified direction
    {
    dir=toupper(dir);
    if(dir!='S' && dir!='N' && dir!='E' && dir!='W')return false;
    
    ast.dir=dir;
    
    return Move();    
    }
    
    
    bool Move() //attempt a move
    {
    //move forward based on facing direction
    point2D before=ast;
    
        switch(toupper(ast.dir))
        {
        case 'S':
            if(mapdata[ast.x][ast.y+1])ast.y++;           
        break;
        case 'N':
            if(mapdata[ast.x][ast.y-1])ast.y--;          
        break;            
        case 'E':
            if(mapdata[ast.x+1][ast.y])ast.x++;         
        break;  
        case 'W':
            if(mapdata[ast.x-1][ast.y])ast.x--;        
        break;                  
        }
    if(ast==before)return false;//return false if we did not move
    
    moves.push(ast);
    
    return true;
    }
    
    //turn around - takes R or L as arguments
    void Turn(char lr)
    {
    lr=toupper(lr);
        
        if(lr=='L')
        {
        if(ast.dir=='S')ast.dir='E';
        else if(ast.dir=='E')ast.dir='N';
        else if(ast.dir=='N')ast.dir='W';
        else if(ast.dir=='W')ast.dir='S';            
        }
        else
        {
        if(ast.dir=='S')ast.dir='W';
        else if(ast.dir=='W')ast.dir='N';
        else if(ast.dir=='N')ast.dir='E';
        else if(ast.dir=='E')ast.dir='S';           
        }
    }
    
    //is maze completed
    bool IsFinished()
    {
    if(ast==end)return true;
    return false;
    }
    
    //puts character back to starting position
    void Reset()
    {
    ast=start;
    }
    
    stack GetSteps()
    {
    return moves;
    }

};//end Map class








int main()
{   
char option;
char mode;

cout<<"To move through the maze manually, press 1, to move with the AI press 2

";
    do
    {
    mode=getch();
    }while(mode!='1' && mode !='2');

if(mode=='2')cout<<"Use 4 to follow left wall and 6 to follow right wall
";
else cout<<"use 4 to turn left, 6 to turn right and 8 to go forward
";


Map map(219);
if(!map.LoadFile("map.txt"))
{
cout<<"Could not find map.txt file";
system("pause");
return 1;
}


map.Display();


while(!map.IsFinished())
{
option=getch();

    if(mode=='1')
    {
    if(option=='4')map.Turn('L');
    if(option=='6')map.Turn('R');
    if(option=='8')map.Move();
    }
    else
    {
    char turndir;
    char revturndir;
    
        //set direction to turn, and oposite, for if the turn did not work
        if(option=='4')
        {
        turndir='L';
        revturndir='R';
        }
        if(option=='6')
        {
        turndir='R';
        revturndir='L';
        } 
        
        map.Turn(turndir);
        while(!map.Move())
        {
        map.Turn(revturndir);    
        }

    }
    
system("cls");   
map.Display();   
}
    


cout<<"Congratulations!  The maze is now complete!

Press any key to analyse stack for an optimal path.";
getch();    

map.Reset();


//optimize the path by manipulating the stack recording

stack orgstack = map.GetSteps();
stack main;

    while(!orgstack.isempty())
    {
    main.push(orgstack.pop());
    }


//shift data between two temp stacks, removing duplicates


//(could not figure this part out)







    //walkthrough again using the stack
    char movedir;
    point2D movement;
    while(!map.IsFinished())
    {
    getch();
    movement=main.pop();
    
    map.Move(movement.dir);
        
    system("cls");   
    map.Display();     
    }

cout<<"
Maze completed";
getch();

return 0;
}

Code: Select all

struct Item
{
point2D position;
Item * next;
};



class stack
{
private:
    Item * top;
    point2D blank;       
    
public:
    stack();
    point2D pop();       //pops a point2D object off the stack
    void push(point2D);  //return inserts a new point2D object to the stack
    bool isfull();       //returns true if it's full
    bool isempty();      //returns true if it's empty
};


stack::stack()
{
top=NULL;
}



point2D stack::pop()
{ 
point2D toreturn;

if(top==NULL)return blank;

toreturn=top->position;

Item * temp=top;

top = top->next;

delete temp;

return toreturn;
}



void stack::push(point2D toadd)
{  
if(isfull())return;

Item * tmp = new Item;

tmp->next=top;
tmp->position=toadd;

top = tmp;
}



bool stack::isfull()
{
Item * temp = new Item;
if(temp==NULL)return true;
    
return false;    
}



bool stack::isempty()
{
if(top==NULL)return true;
return false;
}

Code: Select all

/**
 * 
 */
package assignment10;

import java.io.*;
import java.util.Scanner;
import javax.swing.JFileChooser;

/**Program to solve and find the shortest path through a maze and report this path to the user.
 * The application asks the user for the name of a text file that contains the maze description
 * reads the maze description from the file
 * computes the shortest path through the maze (the shortest path to any given point)
 * and counts the exact number of steps taken to reach the end from the start point
 * 
 * @author Curtis B. Chapman
 * @date 11/18/2008
 * @version 1.2
 * 
 */

public class MazeSolver
{
    public static void main (String[] args)
    {

        // input from user filename
        JFileChooser chooser = new JFileChooser(new File("C:\Users'Curtis'Desktop"));
        int result = chooser.showOpenDialog(null);
        {
            if (result == JFileChooser.CANCEL_OPTION)
                return;

            File mazeFile = chooser.getSelectedFile();

            // read file & build maze
            Scanner s;
            try
            {
                s = new Scanner(mazeFile);

                Maze m = new Maze(s);

                // solve
                String shortestPath = m.getShortestPath();
                System.out.println(shortestPath);

                // print results
                System.out.println("");
                System.out.println("Maze width: " + m.getWidth());
                System.out.println("Maze height: " + m.getHeight());
                System.out
                        .println("Maze start point is at row: " + m.getStartRow() + " and column: " + m.getStartCol());
                System.out.println("Maze end point is at row: " + m.getEndRow() + " and column: " + m.getEndCol());
                System.out
                        .println("The shortest path through the maze takes " + (int) shortestPath.length() + " steps");

            }
            catch (IOException e)
            {
                System.out.println ("Unable to read the file -- program terminated.");
                return;            
            }
        }
    }
}

Code: Select all

package assignment10;

import java.util.Scanner;

/**Program to solve and find the shortest path through a maze and report this path to the user.
 * The application asks the user for the name of a text file that contains the maze description
 * reads the maze description from the file
 * computes the shortest path through the maze (the shortest path to any given point)
 * and counts the exact number of steps taken to reach the end from the start point
 * 
 * @author Curtis B. Chapman
 * @date 11/18/2008
 * @version 1.2
 */

public class Maze
{
    private boolean[][] isWall;
    private int         width, height;
    private int         startRow, startCol, endRow, endCol;
/**Sets the width and height of the maze based off the scanned in file
 * 
 * @param Sets the width and height of the maze based on the scanned file
 */
    public Maze (Scanner s)
    {
        width = s.nextInt();
        height = s.nextInt();
        isWall = new boolean[height][width];

        for (int row = 0; row < height; row++)
        {
            // finds start point, end point, and wall locations
            String rowChars = s.next().toUpperCase();
            for (int col = 0; col < width; col++)
            {
                // sets walls as characters that equal '#'
                char ch = rowChars.charAt(col);
                isWall[row][col] = ch == '#';
                // sets start point
                if (ch == 'S')
                {
                    startRow = row;
                    startCol = col;
                }
                // sets end point
                else if (ch == 'E')
                {
                    endRow = row;
                    endCol = col;
                }
            }
        }
    }


    /**Returns the width
     * 
     * @return the width
     */
    public int getWidth ()
    {
        return this.width;
    }

    /**Returns the height
     * 
     * @return the height
     */
    public int getHeight ()
    {
        return this.height;
    }

    /**Returns the start row
     * 
     * @return the startRow
     */
    public int getStartRow ()
    {
        return this.startRow;
    }

    /**Returns the start column
     * 
     * @return the startCol
     */
    public int getStartCol ()
    {
        return this.startCol;
    }

    /**Returns the end row
     * 
     * @return the endRow
     */
    public int getEndRow ()
    {
        return this.endRow;
    }

    /**Returns the end column
     * 
     * @return the endCol
     */
    public int getEndCol ()
    {
        return this.endCol;
    }
    /**Checks if space is a wall or boundry
     * 
     * @param row edge = wall
     * @param col edge = wall
     * @return true if wall
     */
    public boolean isWall (int row, int col)
    {
        if (row<0 || row >=height || col <0 || col >= width)
            return true;
        return isWall[row][col];
    }
    
   /** Finds the shortest path to every cell in maze
    * 
    * @return path to given cell in maze
    */
    
    public String getShortestPath()
    {
        String[][] path = new String [height][width];
        path[startRow][startCol]= "";
        boolean changed = true;
        while (changed)
        {
            changed=false;
            for (int row =0; row <height; row ++)
                for (int col = 0; col <width; col ++)
                {
                    //North
                    if (!isWall(row-1,col) && path[row-1][col] !=null && (path [row][col] == null || path[row][col].length() > path[row-1][col].length()+1))
                    {
                        path[row][col]= path [row-1][col]+ "S";
                        changed = true;
                    }
                    //South
                    if (!isWall(row+1,col) && path[row+1][col] !=null && (path [row][col] == null || path[row][col].length() > path[row+1][col].length()+1))
                    {
                        path[row][col]= path [row+1][col]+ "N";
                        changed = true;
                    }
                    //East
                    if (!isWall(row,col-1) && path[row][col-1] !=null && (path [row][col] == null || path[row][col].length() > path[row][col-1].length()+1))
                    {
                        path[row][col]= path [row][col-1]+ "E";
                        changed = true;
                    }
                    //West
                    if (!isWall(row,col+1) && path[row][col+1] !=null && (path [row][col] == null || path[row][col].length() > path[row][col+1].length()+1))
                    {
                        path[row][col]= path [row][col+1]+ "W";
                        changed = true;
                    }
                }
        }
        System.out.println("The path taken from Start to Finish is: " );
        return path[endRow][endCol];
    }
    
}