Aravind Sundararajan

Project Overview

Pokemon Egg Move Calculator is a sophisticated web application that solves one of the most complex problems in Pokemon breeding: finding the shortest possible breeding chains to transfer specific moves between Pokemon species. This project was developed in collaboration with the University of Illinois Data Driven Discovery Group.

The project provides a comprehensive solution for:

• Breeding Chain Optimization: Find the shortest path to transfer any egg move
• Graph Theory Application: Model Pokemon breeding as a directed graph problem
• Data-Driven Analysis: Process comprehensive Pokemon move and breeding data
• Interactive Web Interface: User-friendly tool for Pokemon trainers and breeders
• Research Collaboration: Academic project with real-world gaming applications

Core Problem

In Pokemon games, certain moves can only be learned through breeding, creating complex multi-step breeding chains. For example, to give Bulbasaur the move "Sludge" (which it cannot learn by leveling or TM), you need to find a chain of Pokemon that can breed with each other, starting from a Pokemon that naturally learns Sludge and ending with Bulbasaur.

Key Innovation

What makes this project particularly interesting is its application of graph theory to solve a real-world gaming problem. By modeling Pokemon breeding relationships as a directed graph with 917 nodes and 46,145 edges, the system can efficiently find all possible shortest breeding chains using modified breadth-first search algorithms.

System Architecture

The Pokemon Egg Move Calculator employs a multi-layered architecture that combines data processing, graph construction, and web interface components.

Core Components

Data Processing Pipeline

1. Data Collection: Scrape Pokemon move data, egg groups, and breeding compatibility
2. Graph Generation: Create adjacency lists for each move's breeding network
3. Index Mapping: Convert Pokemon names to unique indices for efficient processing
4. Path Computation: Apply graph algorithms to find breeding chains
5. Result Presentation: Display optimized breeding paths to users

Project Structure

pokemon-egg-move-calc/
├── data/                           # Processed Pokemon data
│   ├── pokemonEggMove.json        # Complete egg move database
│   ├── egg_groups.csv             # Pokemon breeding groups
│   ├── pokemonNames.csv           # Pokemon name mappings
│   └── adjLists/                  # Graph adjacency lists
├── methods-and-scripts/           # Core algorithms
│   ├── emc.py                     # Main path finding algorithm
│   ├── make_adjlists.py           # Graph construction
│   ├── eggMoveScrape.py           # Data scraping
│   └── emc.js                     # JavaScript implementation
└── sandbox/                       # Development and testing

Key Features

1. Comprehensive Move Database

Complete coverage of all Pokemon moves and breeding mechanics:

• All Pokemon Species: Coverage of 917 Pokemon across all generations
• Complete Move Lists: Every move that can be learned through breeding
• Egg Group Mapping: Detailed breeding compatibility relationships
• Multiple Learning Methods: Level-up, TM, and breeding move tracking

2. Advanced Graph Algorithms

Sophisticated path finding for optimal breeding chains:

• Shortest Path Discovery: Find the most efficient breeding chains
• Multiple Path Options: Present all possible shortest paths
• Directed Graph Modeling: Accurate representation of breeding relationships
• Efficient Search: Optimized algorithms for large-scale graph traversal

3. Interactive Web Interface

User-friendly tool for Pokemon trainers and breeders:

• Pokemon Selection: Easy-to-use dropdown menus for Pokemon and moves
• Visual Chain Display: Clear presentation of breeding steps
• Real-time Computation: Instant results for any Pokemon-move combination
• Cross-platform Access: Works on any modern web browser

4. Research and Academic Applications

Demonstrates practical applications of computer science concepts:

• Graph Theory Implementation: Real-world application of network algorithms
• Data Science Pipeline: End-to-end data processing and analysis
• Web Development Integration: Full-stack application development
• Academic Collaboration: University research project with practical outcomes

Technology Stack

Core Technologies

Data Sources

• Pokemon Database: Comprehensive move lists and breeding data
• Egg Group Information: Breeding compatibility relationships
• Move Learning Methods: Level-up, TM, and breeding move tracking
• Pokemon Images: Visual assets for the web interface

Development Tools

• Web Scraping: Automated data collection from Pokemon databases
• Data Processing: CSV and JSON manipulation for graph construction
• Version Control: Git for collaborative development
• Testing Framework: Comprehensive testing of algorithms and data integrity

Performance Optimizations

• Graph Preprocessing: Pre-computed adjacency lists for fast lookups
• Index Mapping: Efficient Pokemon name to index conversion
• Caching: Store computed paths for frequently requested combinations
• Algorithm Optimization: Modified BFS for shortest path discovery

Algorithm Details

Graph Construction Process

The system builds a directed graph where nodes represent Pokemon and edges represent breeding compatibility:

# Graph construction for each move
for moveFileName in os.listdir("../data/moves/"):
    with open('../data/moves/' + moveFileName, 'rb') as moveFile:
        moveData = list(reader)
        
        # Extract source and target nodes
        sourceNodes = []  # Pokemon that learn move by level-up/TM
        targetNodes = []  # Pokemon that learn move by breeding
        
        # Check breeding compatibility
        for source in sourceNodes:
            for target in targetNodes:
                if share_egg_group(source, target):
                    add_edge(source, target)

Path Finding Algorithm

The system uses a modified breadth-first search to find all shortest breeding chains:

# Find all shortest paths
G = nx.read_adjlist(desiredMove + '.adjlist', create_using=nx.DiGraph())

all_paths = []
for pokemon in source_pokemon:
    try:
        paths = nx.all_shortest_paths(G, source=pokemon, target=desiredPokemon)
        all_paths.extend(paths)
    except nx.exception.NetworkXNoPath:
        continue

# Remove duplicates and display results
output = list(set(all_paths))
for path in output:
    print(" => ".join(path))

Graph Statistics

Complexity Analysis

• Time Complexity: O(V + E) for BFS traversal
• Space Complexity: O(V) for storing visited nodes
• Preprocessing: O(M × V²) for graph construction
• Query Time: O(V + E) for path finding

Usage Guide

Web Interface Usage

The live web application provides an intuitive interface for finding breeding chains:

Example Breeding Chain

To give Bulbasaur the move "Sludge":

Command Line Usage

For developers and advanced users, the Python implementation can be run locally:

# Run the egg move calculator
python emc.py

# Enter the desired move and Pokemon when prompted
Which egg move are you interested in? Sludge
Which Pokemon would you like to breed Sludge onto? Bulbasaur

# View the computed breeding chains
Possible breeding chains are as follows:
Koffing => Shellos => Mudkip => Bulbasaur

Data File Structure

data/
├── pokemonEggMove.json        # Complete egg move database
├── egg_groups.csv             # Breeding group assignments
├── pokemonNames.csv           # Pokemon name mappings
├── adjLists/                  # Pre-computed graph files
│   ├── Sludge.adjlist         # Breeding graph for Sludge
│   ├── Thunderbolt.adjlist    # Breeding graph for Thunderbolt
│   └── ...                    # One file per egg move
└── moves/                     # Individual move data files
    ├── Sludge.csv             # Pokemon that learn Sludge
    └── ...                    # One file per move

Development

Project Timeline

This project was developed as a collaborative effort with the University of Illinois Data Driven Discovery Group:

Collaboration Details

Technical Challenges

• Data Complexity: Managing relationships between 917 Pokemon and hundreds of moves
• Graph Scale: Efficiently processing 46,145 breeding relationships
• Algorithm Optimization: Finding shortest paths in large directed graphs
• Data Accuracy: Ensuring breeding mechanics match Pokemon game rules
• Web Performance: Providing real-time results for complex queries

Future Enhancements

• Multi-Generation Support: Include Pokemon from newer game generations
• Advanced Filtering: Filter chains by Pokemon availability or breeding difficulty
• Visual Improvements: Enhanced chain visualization with Pokemon sprites
• Mobile Optimization: Responsive design for mobile devices
• API Development: RESTful API for third-party integrations

Academic Impact

This project demonstrates the practical application of computer science concepts in gaming and entertainment:

• Graph Theory Application: Real-world use of network algorithms
• Data Science Pipeline: End-to-end data processing and analysis
• Web Development: Full-stack application with modern technologies
• Research Collaboration: Cross-disciplinary academic project