Algorithm

This algorithm finds all best paths (in most cases) and move ants from the start room to the end room in an optimal way (with the least amount of turns).

Step I: Parse map file and validate received data

Requirement for map:

1. Map must have a valid number of ants: 1 <= number of ants <= INT_MAX.

2. Map must have start and end rooms.

3. Map must have no rooms with the same names. Each room name must be unique.

4. Map must have no rooms with the same coordinates.

5. Map must have one or more links.

6. Each link must have valid names of start and end rooms. It means that rooms with these names are present in map file.

7. Map must have no duplicates of links. There are no links that connect the same points.

Seventh requirement means that map file cannot have the following lines:

dining_room-living_room
// a few other links
living_room-dining_room

Also these lines are not possible too:

dining_room-living_room
// a few other links
dining_room-living_room

To help understand created algorithm some steps have images with example map, that display it after work current part of algorithm. For example, we received the following map:

Step II: BFS (Breadth-first search)

At this step I use BFS algorithm. But my point is not to find out the shortest path. My point is to find out levels that this algorithm assigns to rooms.

Rooms are called vertices in a graph theory. Links are called arcs.

If you know Russian, you can check this video about how BFS algorithm works. It provides a good explanation.

I use BFS algorithms as it is, but with one little change — end room will get MAX_INT as BFS level.

It is important for correct algorithm work.

Step III: Delete useless links

Which links are useless?

• Peer-to-peer links. (Links that connect rooms with the same BFS level)
• Links which start or end room has no BFS level (BFS level assigned to -1 during initialization).

Step IV: Align links

At this step we have to align our links. It means that all links have has the following structure:

room with BFS level N-room with BFS level M, where N < M.

At this step each link will receive direction.

I use this step to prepare received data to the next step.

Step V: Count input and output links for each rooms

Step VI: Delete dead ends

At this step we have to delete all links to the rooms that have zero links of one type, but have one or more links of another type. For example, links to room, that has 2 input links and 0 output links, will be deleted.

Step VII: Delete input forks

Step VIII: Delete output forks

Step IX: Form paths

Step X: Execute turns (Move ants from start to end room)