Lem-in

A digital ant farm simulation written in Go.

I built this project to solve a complex pathfinding and maximum flow problem. The goal is to move n ants from a Start Room to an End Room through a network of tunnels in the fewest number of turns possible.

The program reads a colony map from a file, calculates the optimal disjoint paths (handling traffic jams and bottlenecks), and outputs the precise movements of each ant.

Features

• Pathfinding Algorithm: Finds the most efficient combination of paths to maximize flow (likely using BFS or Edmonds-Karp logic).
• Strict Validation: robustly handles errors, including invalid coordinates, duplicate rooms, self-loops, and broken links.
• Traffic Management: Ensures ants never collide or step on each other (except in Start/End rooms).
• Web Visualiser: Includes a custom-built HTML visualiser to watch the colony in action.

Usage

Prerequisites

• Go (Golang) installed on your machine.

1. Running the Simulation

Run the program by passing a map file as an argument. I have included sample maps in the testdata/ folder.

go run . testdata/test1.txt

Using the Visualiser (Bonus)
I included a visualiser tool that generates an animation of the ants. Pipe the output of the main program into the visualiser script:

go run . testdata/test1.txt | go run visualizer/main.go

This will create a file named ant-farm.html. Open it in your browser to watch the simulation!

Input Format
The program expects a file with the following structure:

Number of Ants: Integer on the first line.

Rooms: Name X Y (e.g., RoomA 23 4).

Tunnels: Name1-Name2 (e.g., RoomA-RoomB).

Start/End: Defined by ##start and ##end tags.

Example Map:
3
##start
1 23 3
2 16 7
3 16 3
##end
0 9 5
0-4
0-6
1-3
4-3
5-2
3-5

Output Format
The program outputs the map content followed by the solution. Each line represents a single turn. Format: Lx-y, where x is the Ant ID and y is the Room Name.

Example Output:
L1-2 L2-3
L1-1 L2-1 L3-2
L3-1

.
├── testdata/           # Sample colony maps for testing
├── visualizer/         # Source code for the web visualiser
├── graph.go            # Graph data structures and initialisation
├── parser.go           # Input file parsing and validation
├── solver.go           # Pathfinding logic and ant queue management
├── main.go             # Entry point
└── README.md

Technical Details
Language: Go (Golang)

Dependencies: Standard Library only (no external packages).

Visualiser: Embedded HTML/JS template generated directly from Go.

🚀 Performance
I optimised the pathfinding algorithm for speed, ensuring it handles graph traversals efficiently without memory leaks.

Benchmark,Iterations,Time per Op
BenchmarkLemIn,85,13.8 ms

Run the benchmark yourself:
go test -bench=.