TME 2
Pathfinding and Decision Making
Game 1: A* Pathfinding (50 marks)
The objective of this work is to implement a game with a tiled search area that has obstacles. The search
area is a 16x16 grid with some obstacles, a start point and a goal point. The robot character (an ant)
should find its way from the start point (home) to the goal point (food) with minimal costs. The search
area has different types of terrains with different cost values as specified in the following table:
Open Terrain Cost = 1
Grassland Cost = 3
Swampland Cost = 4
Obstacles Not applicable
Your program must allow the user to specify the grid configuration at the beginning of each run. So the
user will have to specify the following elements:
the start and the goal cells
the obstacle cells
the nature of terrain for each cell
Also your program should allow the user to view the path search evolution from the start point to the final
point.
Game 2: Finite State Machine (50 marks)
The objective of this work is to implement a game simulating the behaviour of ants. The ants should be
designed based on the logic that their purpose is to collect food and return to their home position. The ants
will have to overcome certain obstacles and follow rules in the simulation:
1. The ants will move randomly in their environment in an attempt to locate a piece of food.
2. Once an ant finds a piece of food, it will return to its home position. You can implement the path to
home position as you wish.
3. When it arrives home, the ant will become thirsty, drop its food, and start a new search for water.
4. The ants looking for water also roam randomly in their environment in an attempt to find water.
5. Once an ant finds water, it drinks and resumes its search for more food.
6. New ants will be born in the colony. Every time an ant returns food to the home position there is a new
ant added to the team that will start a search for food.
7. The ant population will continue to grow as long as more food is brought home.
8. The environment is a grilled area with cells that may be of different
types: empty ground, food, water, or poison.
9. The food, water, and poison are randomly placed in the environment.
10. The ants can walk safely on the empty ground, food, and water cells; however any ant who stepps on
a poison cell will die.
11. The only thing the user has to specify is the starting number of ants for the colony. The food, water,
and poison should be generated and randomly distributed by the program.
12. The ants must roam randomly when looking for food or water; but you can use your creativity to
implement other movements (i.e. returning to home position).
For each of the games,submit the following files:
Your Java program files
Any sound files used in your program
Any textures or images used in your program
A description file where you describe your game, provide instructions how to compile/run the game, give
the state machine, and describe any bugs/problems in your program.
Marking
Your overall grade for each game will be based on the following:
Fulfillment of the requirement that your program be a working game (20 marks)
Creativity (5 marks)
A description file that contains details about your design and implementation (20 marks)
The design of your code. Is your coding style consistent, readable, commented and modularized? (5
marks)