mdodovic / find-the-treasure Goto Github PK

View Code? Open in Web Editor NEW

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.

Python 100.00%

find-the-treasure's Introduction

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:

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.

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.

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.