• Description
• Getting Started
• Installation
• Program usage
• Generator
• Visualizer
• Internal Architecture
• Optimization
• Built With
• Authorship

Description

Lem_in is a pathfinding simulation project in C where you must help a group of ants travel from the entrance (##start) to the exit (##end) of an anthill through a complex system of rooms and tunnels.

The goal: get all ants to the exit in the fewest possible turns.

Game Rules

• Each ant can move only once per turn.
• Each room can only contain one ant at a time, except for ##start and ##end which can contain multiple.
• Ants follow the shortest available paths while avoiding collisions and traffic jams.
• The challenge is to parse the map, compute all viable routes, then schedule the ants’ movement efficiently.

---

Getting Started

These instructions will help you install, compile, and run the project on your local machine. See Program Usage for execution examples.

Prerequisites

• gcc
• make
• python3
• pygame
• perl (optional for map generation)

Fedora:

sudo dnf install gcc make

Ubuntu / Debian:

sudo apt-get install gcc make python3

Arch:

sudo pacman -S gcc make python-pip

macOS:

brew install gcc make python3
pip install pygame

---

Installation

Clone this repository and enter it:

git clone https://github.com/lelouchzr/lem_in && cd lem_in/

Compile the project:

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make
cd ..

---

Program Usage

Lem_in expects a valid map from stdin:

./lem_in < maps/map.txt

Where map.txt contains:

1. Number of ants
2. Room definitions with coordinates
3. Tunnel connections
4. Special commands ##start and ##end

Example

3
##start
A 0 0
B 1 0
C 2 0
##end
D 3 0
A-B
B-C
C-D

---

Generator

A Perl script allows custom map generation:

perl generator.pl size density ant_count > name_map.txt

---

Visualizer

The visualizer (Python 3 + pygame) accepts a lem_in trace as input and simulates the ant movement.

python3 src/main.py maps/example.txt

Controls

Key	Function
Esc	Exit
Space	Advance by one step
T	Toggle tunnel visibility
A	Toggle auto-play mode (only available at simulation start)
← / →	Decrease / Increase simulation speed

---

Internal Architecture

Parsing (in src/parsing/)

The input is parsed line by line with getline(), respecting strict formatting and error handling:

• Each line is validated: number of ants, rooms (name & coordinates), tunnels (bi-directional).
• Commands (##start, ##end) are used to assign special room roles.
• The parsing uses:
  • Custom linked lists (ll_string, ll_void)
  • A custom hashmap to store rooms by name for O(1) lookup
  • Graceful handling of malformed input with exit(84) on error

This ensures robust, linear-time parsing even on large maps.

Graph Construction (in src/graph/)

• Each room is represented as a t_room structure.
• Tunnels are stored as adjacency lists.
• The custom hashmap enables:
  • Quick existence checks during parsing
  • Fast room resolution for tunnel creation
  • Efficient memory footprint

Pathfinding Algorithm (in src/algorithm/)

• Uses Breadth-First Search (BFS) to find the shortest paths between start and end.
• Tries to find multiple disjoint paths (no overlapping rooms) for parallel ant movement.
• Each path's length is tracked to optimize the distribution of ants.

Ant Movement Scheduler

• Once paths are selected, ants are assigned optimally:
  • Shorter paths get more ants
  • Movement is simulated turn by turn, ensuring:
    • No collisions
    • Minimal steps to finish
• Output follows the required format:

L1-B L2-B
L1-C L2-C L3-B
L1-D L2-D L3-C
L3-D

---

Optimization

• Parsing: custom memory management & linked list utilities for performance and clarity
• Lookup: custom hashmap for O(1) access to rooms by name
• Scheduling: ants are split across paths to minimize the total number of turns

---

Built With

• C – Main engine
• Python3 – Visualizer
• Pygame – Visual display

---

Authorship

We have decided not to display personal names or email addresses in this project repository. To maintain privacy, no co-author metadata was added to commits. Each team member has independently published this project in a repository under their personal GitHub profile.