If you have cloned the BZRFlag repository, be sure that you pull before starting work on this lab! I have made several updates that you need in order for this lab to work (as of May 6, commit 7f7a45c…, it should work).

As before, you will use bzrflag as a framework for your searches. However, bzrflag models a continuous world. Before we can use any of the search techniques which we discussed in class, we need to “discretize” the world. You will use the occgrid command in the BZRC Protocol to make a grid of spaces.

You will need to create a structure to represent this search space. Since the whole point of searching is to find a valid path to the goal, you will need to mark the search states that are occupied by obstacles (occgrid tells you this). Your search must not visit these nodes.

Your code must work on any map (see the maze1.bzw in the maps directory of bzrflag, for example). Your code should also work for any level of discretization. The occgrid in bzrflag uses a fixed level of discretization, one square for every meter in the world (if the world size is 800 by 800, for example, we have 640000 nodes in the graph). When you ask the server for the occgrid, it will give you back a matrix. Use that matrix as your graph for your search.

Because 640000 nodes is a lot of nodes in the graph, we will be using a smaller world size for this lab (and this lab only). This is the command you need to run when you pass off (though you can play around with other maps and world sizes if you feel like it):

bin/bzrflag --world-size=400 --world=maps/small_maze1.bzw --occgrid-width=800 --seed=1 --red-tanks=1 --green-tanks=1

The seed is so that the tanks are initialized in exactly the same spot, so that your code and my code should get exactly the same results, assuming we both coded the algorithms correctly. With a smaller world size you will only have 160000 nodes to deal with, which takes much less time. The occgrid width of 800 means that no matter where your tank is, you will get a graph of the entire world.

My Python code that wasn't meant to be particularly fast took about 15 seconds from startup to showing the path according to A* search. I didn't do gnuplot or graphs, I just printed it out, so yours may be slower than that, but mine was Python - it shouldn't be much slower for one search. Most of the time was building the graph, anyway, so doing multiple searches shouldn't take too much longer, either.

Also, when you do searches in future labs (and you definitely should), you almost certainly should not discretize the world this way; it's way more granular than you need and takes way too long to be reasonable during an actual game (plus you probably won't have access to such a nice occgrid command). This is just to get some practice with searching. That also probably means you want to keep your search code separate from your build-the-graph code, so you can reuse your search code with a different graph for future labs.

You will implement several different searches to find a path from your current position (the search state you are currently in) to the enemy flag (the search state that contains the flag). You will implement the search algorithms listed above.

For each search, you will draw lines when you expand a node (showing which children will be considered). You will also draw lines in the world indicating which path is ultimately chosen. You will draw these using gnuplot as you did to draw your fields in Lab 1.

You do not have to move your tank along the search path yet (that will be in the next lab). You only have to display the progress of your search and the final path.

From any state you may go to a neighboring state or a diagonally neighboring state. Please consider these states in the following order: left (x-1,y), right (x+1,y), up (x,y+1), down (x,y-1), diagonal up-left, up-right, down-left, down-right. Remember also that your search space is a graph. Use the graph search code (see section 3.5 of the book) so that you do not repeat states. Since you will generally have come from one of your 8 neighbors, there will generally be 7 or fewer places you can go next.

For the Greedy and A* searches, you should use the distance as the cost (diagonal moves will cost more (<math>\sqrt{2}</math>) than non-diagonal moves).

There are areas that you do not want to get close to. You must also have an option that allows you to increase the costs of space you travel through that is close to obstacles (“penalized mode”). You will run your code both with and without “penalized mode” set.

“Penalized mode” should work as follows:

• If you are in a cell next to occupied cell (up, down, right, left, or diagonal) moving to another cell next to an occupied cell the cost of movement should be 1.5 times the distance.
• If you are in a cell next to occupied cell (up, down, right, left, or diagonal) moving to another cell NOT next to an occupied cell the cost of movement should be 1.1 times the distance.
• If you are in a cell NOT next to occupied cell (up, down, right, left, or diagonal) moving to another cell next to an occupied cell the cost of movement should be 1.3 times the distance.

Note that the occgrid command will only give you information about obstacles, not about enemy tanks. The “occupied cells” mentioned above should include not only obstacles but also enemy tanks. Use the othertanks command to get that information and incorporate it into your edge costs. You should be able to move an enemy tank to a point along what used to be the optimal path and see that the path changes.

Experiment with these values to see if you can get desirable behavior (obstacle avoidance), report on these values during the pass off. Try changing the penalty in other ways, like slightly penalizing cells 2 cells from an obstacle.

Grading will be done on the basis of the path costs (optimal search algorithms should find the optimal path for a given discretization), memory and CPU usage (just make sure it is not out of control), and the correctness of the visited nodes (number of nodes in the visited/closed list). You will also be graded on your creativity and efforts to find a penalty function that behaves well in the presence of walls, obstacles, and enemy tanks.

A discussion of gnuplot (a tool for drawing the lines in the search) and animation is available here. If you want to use something else to make these drawings, you are welcome to do so, but drawing packages can be a big distraction. Don't spend too much time making your own solution to the drawing problem.

You will need to pass off your lab to the TA. You will do so by demonstrating the following:

• The TA will pick a couple of worlds for you to load that are at least modestly interesting.
• You should be red and your “enemy” should be green. You should find the path from your red tank with index 0 to the green flag. Do your search with penalty off for the uninformed searches, and both on and off for the informed ones. Neither you nor your enemy should move.
• For each search display the paths you tried (nodes popped) AND the final path taken in gnuplot. At the end of each search you should report on the total nodes popped and the cost and length of the final path.
• Demonstrate that you can get better obstacle avoidance by changing the penalty function.
• Using gnuplot animation of the search you should be able to show any increment of steps, so set this to 1 and watch it for a while, verify that things are working, and then kill it and set it higher so that it will actually finish in a reasonable time. Remember that you can drive gnuplot programatically, or make a big file with pause commands between each frame (step in the search), or, if all else fails, you could make a pile of separate gnuplot files (this option is awkward). If you choose to make a file or files, you should also have a way to tell your program to do a limited number of search steps (The whole search would be a very large file).
• For the informed searches allow the TA to control the enemy green agent (i.e. connect with the normal client or just telnet so it can be moved it around). The TA will move it to a place along your original path, then you will connect with your agent, and demonstrate that your path and final cost are altered by the presence of the enemy agent and your new reticence to approach obstacles. The TA must be able to tell that your search is cost sensitive.

It would be appreciated if you could create scripts to easily start these things in order so you can do this quickly. If someone makes a handy bash script, you are welcome to post it here

This lab is again out of 100 points. There is no write up, so your grade will just be based on demonstrating to the TA that your code works. You will get points according to the following scale:

• 15 points each for correctly implementing the five requested search algorithms (a total of 75 points). You will have to demonstrate that your code behaves correctly, and that is most easily done with the visualization described above (i.e., if the TA can tell by looking at your plots that you're doing a correct breadth-first search, you will pass off a lot easier than trying to demonstrate it some other way). For optimal searches, the TA has the correct answers for nodes visited, path cost and length, so your answers should match (we will be lenient with off-by-one errors). A* will be tested on at least two worlds, one of which was mentioned above.
• 15 points for correctly implementing penalized search. 10 points will be given for having a basic implementation of it, and 5 for experimenting and finding a way to penalize that performs well.
• 10 points for visualizing the search with gnuplot or some other tool (these are essentially free points, as passing off the algorithm part pretty much requires the visualization).

I realize also that a 400×400 grid is very hard to visualize all at once - each line for an edge followed would be very small. So, I think it reasonable to demonstrate the behavior of the searches on a small part of the grid next to the starting tank (where it can be larger and more visible), then show the overall result separately. Showing the overall result (a line from the tank to the flag) is important because that's the only way to really tell that the penalization code works properly - the line should change if I move a tank.

You don't need to turn in a lab report for this lab, but please send the TA email with a declaration of how much time was spent by each person in your group on the lab.

<!–To pass off this lab, you will:

• Submit all of your search code electronically to the ta
• Turn in a detailed lab report and a declaration of time spent by each lab partner
• Demonstrate to another team how cool your code works
• Report on how well another teams code worked

This report should be thorough. Go through all of your experiments in such a way that they could be replicated by someone reading your paper. If you have had experience writing conference papers before, make your paper look like one of those, including an abstract, lab context, and details about what you tried. Make sure that your report includes information like what heuristics you used. Try searches with inadmissible heuristics as well and report on the optimality of the resulting searches.

Specifically, you will need to include information about the following:

• What do your searches look like
  • Use gnuplot to draw what paths have been considered at a few times as the search runs (lines to show all paths considered so far)
  • Use gnuplot to draw the final path found.
• How many nodes were expanded (“popped”) and what is the cost of the path found. Include at least one run in a very small case (discretize very coarsely) so that you can demonstrate that you actually implemented the algorithm correctly. Give evidence that your code is doing the right thing.
• What heuristics were used along with the results of their application
• What happens when an inadmissible heuristic is used (give concrete results)
• What have you learned about the use of search in the bzrlag environment, What might you use in your final bzrflag agent. specifically:
  • How you would discretized the world for use later in this class?
  • How you would measure edge costs? Penalized? If so, How?
  • What heuristic(s) you would use?
• Your report also needs to include a section on the tests that you performed with the other group. You must report on all search algorithms. Include sections on:
  • The situation and the results your code achieved in the tests they set up
  • The situation and the results they achieved in the tests you set up for them
  • Please be candid in your discussion in both cases

Perhaps most importantly, put your results into a format that is easy to understand at a glance. Some- times that means that you want to put things into a graph, and sometimes it doesn’t. Be creative, and consider that your audience wants to get maximum understanding with a minimum of effort.–!>

Thanks to Chris Monson, Andrew McNabb, David Wingate and Kirt Lillywhite