Program How To:
When opening my program first use File -> open. Then select a text file. The requirements of the text file are that it must have numbers ranging from 0-4 separated by spaces and new rows with the "enter" or "return" key. The numbers have the following meaning:
0 - Empty Space
1 - Wall
2 - Robot block (movable block, will only accept the first robot in file. All others are treated as walls)
3 - Target block (Can only be pushed by robot)
4 - Goal (target will disappear upon being pushed to this location)
The colors of the blocks are also as follows
White - 0 - Empty space
Black - 1 - Wall
Blue - 2- Robot
Red - 3 - Target
Green - 4 - Goal
Grey - Visited (used in execution of search algorithms)
The application has the following buttons at the top of the page. File, Reset, MoveToGoal, Manual Movement and Display.
Reset will reset all of the blocks being displayed to what the file originally contained.
MoveToGoal contains the available searches. These are as follows
DFSRobot - performs a Depth First Search on the Robot block to a goal location.
DFSTarget - pushes all of the target blocks in the file to goal destinations using the depth first search search technique.
DLSRobot - performs an iterative deepening depth limited search on the robot block.
DLSTarget - pushes all of the target blocks to goal locations using the iterative deepening depth limited search technique. Currently if the target block becomes stuck this uses a DFS to reset to the previously valid state instead of a DLS.
Manual Movement - Allow user control of the robot block with either WASD or the arrow keys.
Display contains some fun functions just for the user to use
Show All - sets the color of the EMPTY spaces to white.
Hide All - sets the color of the EMPTY spaces to black. This gives the user the feel of what the computer knows in an uninformed search strategy. However it would also not know the goal or target block locations. But making goal and target block locations black made this a little too confusing to use.
Show Visited - spaces previously occupied by the robot block will be grey instead of white
Hide Visited - spaces previously occupied by the robot block will be white (as normal)
As a side note. In order to use the show/hide visited feature for manual movement you must first enable manual movement. As currently all of the features are set to default upon enabling/disabling manual movement.
Improvements to be made:
currently the display to the screen is not implemented on its own thread so the size of the application will affect execution speed.
Writing to the log is also not on its own thread so as execution occurs the next move will be slightly slower.
Execution of searches
When the searches are being executed the robot will have mark visited spaces with grey squares. If a target block is pushed to a point where it is not possible to move any further the application will reset to the last valid state. To do this it saves the valid target movement directions to a stack and then runs the depth first search to move the robot and targets until the most recent valid state is reached. This is a problem for the DLSTarget because it is not truly following the most efficient path that it found. The problem I had was figuring out how to properly add the valid robot moves to a stack to retrace because I had tried merging two stacks together. The problem was when reaching a fail state removing only the correct states off of the stack containing all of the valid robot moves.
When opening my program first use File -> open. Then select a text file. The requirements of the text file are that it must have numbers ranging from 0-4 separated by spaces and new rows with the "enter" or "return" key. The numbers have the following meaning:
0 - Empty Space
1 - Wall
2 - Robot block (movable block, will only accept the first robot in file. All others are treated as walls)
3 - Target block (Can only be pushed by robot)
4 - Goal (target will disappear upon being pushed to this location)
The colors of the blocks are also as follows
White - 0 - Empty space
Black - 1 - Wall
Blue - 2- Robot
Red - 3 - Target
Green - 4 - Goal
Grey - Visited (used in execution of search algorithms)
The application has the following buttons at the top of the page. File, Reset, MoveToGoal, Manual Movement and Display.
Reset will reset all of the blocks being displayed to what the file originally contained.
MoveToGoal contains the available searches. These are as follows
DFSRobot - performs a Depth First Search on the Robot block to a goal location.
DFSTarget - pushes all of the target blocks in the file to goal destinations using the depth first search search technique.
DLSRobot - performs an iterative deepening depth limited search on the robot block.
DLSTarget - pushes all of the target blocks to goal locations using the iterative deepening depth limited search technique. Currently if the target block becomes stuck this uses a DFS to reset to the previously valid state instead of a DLS.
Manual Movement - Allow user control of the robot block with either WASD or the arrow keys.
Display contains some fun functions just for the user to use
Show All - sets the color of the EMPTY spaces to white.
Hide All - sets the color of the EMPTY spaces to black. This gives the user the feel of what the computer knows in an uninformed search strategy. However it would also not know the goal or target block locations. But making goal and target block locations black made this a little too confusing to use.
Show Visited - spaces previously occupied by the robot block will be grey instead of white
Hide Visited - spaces previously occupied by the robot block will be white (as normal)
As a side note. In order to use the show/hide visited feature for manual movement you must first enable manual movement. As currently all of the features are set to default upon enabling/disabling manual movement.
Improvements to be made:
currently the display to the screen is not implemented on its own thread so the size of the application will affect execution speed.
Writing to the log is also not on its own thread so as execution occurs the next move will be slightly slower.
Execution of searches
When the searches are being executed the robot will have mark visited spaces with grey squares. If a target block is pushed to a point where it is not possible to move any further the application will reset to the last valid state. To do this it saves the valid target movement directions to a stack and then runs the depth first search to move the robot and targets until the most recent valid state is reached. This is a problem for the DLSTarget because it is not truly following the most efficient path that it found. The problem I had was figuring out how to properly add the valid robot moves to a stack to retrace because I had tried merging two stacks together. The problem was when reaching a fail state removing only the correct states off of the stack containing all of the valid robot moves.
Explanation of Files:
Main.cs: Display form that controls the input and output of the program. Has many event handlers that will listen for events from both FloorMap.cs and AITestFunctions.cs. The animation is done in a panel on the form which will resize upon the form resize.
FloorMap.cs: Handles file opening and the arrays containing the floor map. Functions are called to manipulate the robot which allow the robot to move north, south, east and west. In order to complete a move the robot will check if it is moving to a valid location within the map. Then it will check if the spot it is trying to move to is a wall, if so it will not move. If it is not a wall it will check if that is a target space. If it is a target block then it will go to check if it is allowed to push the block. If it cannot push the block it will not move, if it can push it will have to check if the spot the target block will move to will be a valid location to move. No AI is contained in this file. Currently the file open function needs to check if the file was empty. If anyone continues my project I believe that this could easily be used by someone else as there is no actual AI being handled in this file. The one exception would be that a check needs to be added in the case of an empty file.
AITestFunctions.cs: Contains the search functions. It contains two versions of each search for the robot. One of the parameters needed to do the search is the FloorMap object. If the search on a target is being completed it will not need to send the floormap object. Four main searches exist within this. The depth first search for the robot and one for the target. The target DFS calls the robot DFS function. I call the iterative deepening depth limited search the robot DLS and the target DLS functions. There is currently a problem with the Target DLS function where I was not able to correctly reset the target when I get stuck so I use the DFS to return to the previous state. It isn't optimal but it at least solves the problem. What I need to change is I need to save all of the robot moves to a stack instead of just saving the robot moves to a stack. Then what I need to do is save the robot moves into a final stack and find a way to properly remove from that stack if stuck.
Main.cs: Display form that controls the input and output of the program. Has many event handlers that will listen for events from both FloorMap.cs and AITestFunctions.cs. The animation is done in a panel on the form which will resize upon the form resize.
FloorMap.cs: Handles file opening and the arrays containing the floor map. Functions are called to manipulate the robot which allow the robot to move north, south, east and west. In order to complete a move the robot will check if it is moving to a valid location within the map. Then it will check if the spot it is trying to move to is a wall, if so it will not move. If it is not a wall it will check if that is a target space. If it is a target block then it will go to check if it is allowed to push the block. If it cannot push the block it will not move, if it can push it will have to check if the spot the target block will move to will be a valid location to move. No AI is contained in this file. Currently the file open function needs to check if the file was empty. If anyone continues my project I believe that this could easily be used by someone else as there is no actual AI being handled in this file. The one exception would be that a check needs to be added in the case of an empty file.
AITestFunctions.cs: Contains the search functions. It contains two versions of each search for the robot. One of the parameters needed to do the search is the FloorMap object. If the search on a target is being completed it will not need to send the floormap object. Four main searches exist within this. The depth first search for the robot and one for the target. The target DFS calls the robot DFS function. I call the iterative deepening depth limited search the robot DLS and the target DLS functions. There is currently a problem with the Target DLS function where I was not able to correctly reset the target when I get stuck so I use the DFS to return to the previous state. It isn't optimal but it at least solves the problem. What I need to change is I need to save all of the robot moves to a stack instead of just saving the robot moves to a stack. Then what I need to do is save the robot moves into a final stack and find a way to properly remove from that stack if stuck.
Executable Program and some test files
| bjkcapstone2017executable.zip |
Entire Project File:
| bryankellycapstone05-08-2017.zip |
Uncompressed code:
|
|
|
|
| ||||||||||
Code in .txt Format
|
|
|
|
| ||||||||||