Underground Navigator

A Windows MFC application for creating and editing subway/metro transit system maps with pathfinding capabilities.

Overview

Underground Navigator is a Visual C++ 6.0 application designed to solve pathfinding tasks on graphs, specifically for transit system maps. It demonstrates a custom implementation of Dijkstra's algorithm using dynamic memory structures.

Key Features:

• Pathfinding: Find optimal routes between two stations on transit maps
• Map Editor: Create and edit custom transit maps with lines, stations, and connections
• Dynamic Data Structures: Pointer-linked lists for efficient memory usage
• Graphics Capabilities:
  • Zoom functionality for loaded maps
  • Pan/move viewport for navigation
  • Optimized screen refresh using shadow device context
• Custom File Format: Save and load maps with version control (.ump format)
• Flexible Styling:
  • Station styles: Circular, Rectangular, Solid, Outline
  • Line styles: Polyline, Rectangle, Ellipse
  • Station states: Active, Under Construction, Disabled, Invisible
• Customizable Appearance:
  • Grid display toggle
  • Adjustable line and station thickness
  • Customizable background and grid colors

Technical Details

Technologies Used:

• Microsoft Foundation Classes (MFC)
• Custom dynamic data structures
• GDI (Graphics Device Interface)
• Binary file I/O

Algorithm: The pathfinding implementation is based on Dijkstra's algorithm, optimized for dynamic memory structures. It uses adjacency lists with temporary and permanent labels to find the shortest path between stations, considering travel time between connections.

Sample Map: The screenshot demonstrates Underground Navigator with the St. Petersburg (Russia) metro map. Sample maps are included in the maps/ directory.

How It Works

1. Create or Load a transit map
2. Mark two stations on the screen as start and destination points
3. Press the search button to calculate the optimal route
4. View results - the best path is highlighted on screen or displayed in a dialog

When creating maps, you can:

• Name lines and stations
• Define travel times between adjacent stations
• Set different styles and states for visual clarity

Use Cases

This application can be used for various transportation networks:

• Subway/Metro systems
• Railway networks
• Airlines routes
• Any graph-based transportation system

Project Structure

• /src - Source code files (C++/MFC)
• /maps - Sample transit map files (.ump format)
• /res - Resources (icons, bitmaps, cursors)
• /demo_assets - Documentation and demo materials
• MapEditor.sln - Visual Studio solution file

Building

This project requires:

• Visual Studio 6.0 or later with C++ and MFC support
• Windows SDK

Open MapEditor.sln in Visual Studio and build the solution.

File Format

Underground Navigator uses a custom binary format (.ump) for storing maps. The format includes:

• Map header (country, region, city, metro name, author, copyright, year)
• Line definitions (geometry, style, status)
• Station definitions (coordinates, names, properties)
• Incidence graph (station connections with travel times)

License

Copyright © 2000-2006. All rights reserved.

---

Demonstrates: MFC, Custom Classes, GDI, File I/O, Graph Algorithms