Skip to content

Game where the agent needs to find the treasure crossing the map with different types of fields, where every cross of the field costs different price depends on the field type.

Notifications You must be signed in to change notification settings

mdodovic/Find-The-Treasure

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

57 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Find-The-Treasure

About the Game

Game represents the squared map where every field is one of the several types. There are 6 types of field, with the given price in the brackets, road (2), grass (3), mud(5), sand(7), water (500) and stone (1000). When you are crossing the field, your path cost is incremented with the appropriate price. Agents need to find the treasure, marked as X on map, using one of the following searching algorithms. Full project description can be found here.

Agents

There are 4 agents, Aki, Jocke, Draza and Bole, and according to this, there are 4 different strategies.

Aki

Aki uses the Depth First Search (DFS) algorithm, with the direction prioriting as the cheapest neighbours field. If the neighbours has the same cost, the direction is priorited in north-east-south-west order. Toy example of DFS algorithm is in the following image:

map0Aki

Jocke

Jocke uses the Breadth First Search (BFS) algorithm, with the direction prioriting as the field whom neighbours, excluding the current field, has the lowest average price.

map0Jocke

Draza

Draza uses the Branch and Bound algorithm, that guarantee the best path from the start to the goal field, using the lowest acumulated price as the criteria of the expanding.

map0Draza

Bole

Bole uses the A* algorithm with the same logic as Draza's approach as far as the accumulated price is considered, while he uses the Manhattan Metric as the heuristics.

map0Bole

Solutions

Some of the agents' paths are shown in the following images:

Map 4

map4Aki

map4Jocke

map4Draza

map4Bole

Map 6

map6Aki

map6Jocke

map6Draza

map6Bole

Map 7

map7Aki

map7Jocke

map7Draza

map7Bole

About

Game where the agent needs to find the treasure crossing the map with different types of fields, where every cross of the field costs different price depends on the field type.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages