McRogueFace integrates with libtcod (The Chron of Doryen) for FOV (field of view), pathfinding, and Dijkstra maps. The integration maintains a synchronized TCODMap that mirrors each grid's walkability and transparency properties.

Parent Page: Grid-System

Related Pages:

AI-and-Pathfinding - Using FOV and pathfinding for game AI
Grid-Rendering-Pipeline - How FOV affects rendering overlays
Entity-Management - Entity perspective and gridstate

Key Files:

src/UIGrid.cpp::syncTCODMap() - Synchronization (lines 343-361)
src/UIGrid.cpp::computeFOV() - FOV computation (line 363)
src/UIGrid.h - TCODMap, TCODPath, TCODDijkstra members

Related Issues:

#64 - TCOD updates (last TCOD sync)
#124 - Grid Point Animation
#123 - Subgrid system integration with TCOD

The World State Layer

TCODMap as World Physics

In the three-layer grid architecture, TCODMap represents world state:

Visual Layer (UIGridPoint) - What's displayed (colors, sprites)
          ↓
World State Layer (TCODMap) - Physical properties (walkable, transparent)
          ↓
Perspective Layer (UIGridPointState) - Per-entity knowledge (discovered, visible)

Every grid has a TCODMap that must be kept synchronized with cell properties.

TCODMap Synchronization

Initialization

When a grid is created, its TCODMap is initialized:

// UIGrid constructor
tcod_map = new TCODMap(gx, gy);
tcod_dijkstra = new TCODDijkstra(tcod_map);
tcod_path = new TCODPath(tcod_map);

// Sync initial state
syncTCODMap();

Synchronization Methods

syncTCODMap() - Full Sync

Synchronizes entire grid:

void UIGrid::syncTCODMap() {
    if (!tcod_map) return;
    
    for (int y = 0; y < grid_y; y++) {
        for (int x = 0; x < grid_x; x++) {
            const UIGridPoint& point = at(x, y);
            tcod_map->setProperties(x, y, point.transparent, point.walkable);
        }
    }
}

Use when: Initializing grid or making bulk changes to many cells.

Performance: O(grid_x * grid_y) - expensive for large grids.

syncTCODMapCell() - Single Cell Sync

Synchronizes one cell:

void UIGrid::syncTCODMapCell(int x, int y) {
    if (!tcod_map || x < 0 || x >= grid_x || y < 0 || y >= grid_y) return;
    
    const UIGridPoint& point = at(x, y);
    tcod_map->setProperties(x, y, point.transparent, point.walkable);
}

Use when: Changing a single cell's properties (e.g., opening a door, destroying a wall).

Performance: O(1) - efficient for incremental updates.

Python API

import mcrfpy

grid = mcrfpy.Grid(grid_size=(50, 50), pos=(0, 0), size=(800, 600))

# Modify cell properties
cell = grid.at((10, 10))
cell.walkable = False  # Block pathfinding
cell.transparent = False  # Block FOV

# Sync to TCOD (required!)
grid.sync_tcod_map()  # Full sync

# Or sync single cell
grid.sync_tcod_cell(10, 10)

Important: Changing cell.walkable or cell.transparent does NOT automatically update TCODMap. You must call sync_tcod_map() or sync_tcod_cell() afterward.

Field of View (FOV)

Computing FOV

FOV determines which cells are visible from a given position:

# Compute FOV from position (25, 25) with radius 10
visible_cells = grid.compute_fov(
    x=25, 
    y=25, 
    radius=10,  # 0 = unlimited
    light_walls=True,  # Walls at FOV edge are visible
    algorithm=mcrfpy.FOV_BASIC  # or FOV_DIAMOND, FOV_SHADOW, etc.
)

# Returns list of (x, y, visible, discovered) tuples
for x, y, visible, discovered in visible_cells:
    print(f"Cell ({x}, {y}) is visible")

FOV Algorithms

libtcod provides several FOV algorithms:

Algorithm	Description	Performance	Use Case
`FOV_BASIC`	Simple raycasting	Fast	General purpose
`FOV_DIAMOND`	Diamond-shaped FOV	Fast	Square grids
`FOV_SHADOW`	Shadow casting	Medium	Realistic lighting
`FOV_PERMISSIVE`	Permissive FOV	Slow	Maximum visibility
`FOV_RESTRICTIVE`	Restrictive FOV	Medium	Minimal visibility

Default: FOV_BASIC provides good balance of speed and realism.

Checking FOV

After computing FOV, check if specific cells are visible:

# Compute FOV first
grid.compute_fov(player.x, player.y, radius=10)

# Check if cell is visible
if grid.is_in_fov(enemy_x, enemy_y):
    print("Player can see enemy!")
    enemy.draw_with_highlight()

Thread Safety: FOV computation is protected by a mutex, allowing safe concurrent access.

Pathfinding

A* Pathfinding

Find shortest path between two points:

# Find path from (5, 5) to (45, 45)
path = grid.find_path(
    x1=5, y1=5,
    x2=45, y2=45,
    diagonal_cost=1.41  # sqrt(2) for diagonal movement
)

# path is list of (x, y) tuples
if path:
    for x, y in path:
        grid.at((x, y)).color = (255, 0, 0, 255)  # Highlight path
    
    # Move entity along path
    entity.path = path
else:
    print("No path found!")

Diagonal Movement Cost

The diagonal_cost parameter affects pathfinding behavior:

1.0 - Diagonal movement is same cost as cardinal (unrealistic, creates zigzag paths)
1.41 (√2) - Diagonal movement costs more (realistic, smoother paths)
2.0 - Diagonal movement very expensive (prefers cardinal directions)
Large value - Effectively disables diagonal movement

# Pathfinding that prefers cardinal directions
path = grid.find_path(10, 10, 20, 20, diagonal_cost=2.0)

# Pathfinding that allows free diagonal movement
path = grid.find_path(10, 10, 20, 20, diagonal_cost=1.0)

Pathfinding Limitations

Static paths: Path is computed once; doesn't update if grid changes
No A customization:* Cannot provide custom cost functions yet
Blocking: Pathfinding is synchronous (blocks Python execution)

Workaround for dynamic obstacles:

# Recompute path periodically
def update_enemy_path(ms):
    # Check if path is still valid
    for x, y in enemy.path:
        if not grid.at((x, y)).walkable:
            # Path blocked, recompute
            enemy.path = grid.find_path(enemy.x, enemy.y, 
                                        player.x, player.y)
            break

mcrfpy.setTimer("path_update", update_enemy_path, 500)  # Every 0.5s

Dijkstra Maps

Computing Dijkstra Maps

Dijkstra maps compute distance from goal(s) to all cells, useful for multi-enemy AI:

# Compute Dijkstra map with player as goal
grid.compute_dijkstra(
    root_x=player.x,
    root_y=player.y,
    diagonal_cost=1.41
)

# Each enemy can now path toward player
for enemy in enemies:
    # Get path to nearest goal (player)
    path = grid.get_dijkstra_path(
        from_x=enemy.x,
        from_y=enemy.y,
        max_length=1  # Just get next step
    )
    
    if path:
        next_x, next_y = path[0]
        enemy.move_to(next_x, next_y)

Multiple Goals

Dijkstra maps support multiple goal cells:

# Find distance to ANY exit
exit_positions = [(5, 5), (45, 5), (5, 45), (45, 45)]

grid.compute_dijkstra_multi(exit_positions, diagonal_cost=1.41)

# Each entity can now path to nearest exit
path = grid.get_dijkstra_path(entity.x, entity.y, max_length=0)  # 0 = full path

Dijkstra vs A*

Feature	A* (find_path)	Dijkstra Maps
Goals	Single target	One or many targets
Computation	Once per path	Once for all entities
Use case	Single entity, single target	Many entities, same target
Performance	O(log n) per entity	O(n) once, then O(1) per entity

Rule of thumb:

1-5 entities → Use A* per entity
10+ entities with same goal → Use Dijkstra map

Entity Perspective System

Gridstate and Discovered/Visible

Each entity can have a gridstate vector tracking what it has seen:

// UIEntity member
std::vector<UIGridPointState> gridstate;

struct UIGridPointState {
    bool discovered;  // Has entity ever seen this cell?
    bool visible;     // Can entity currently see this cell?
};

Setting Entity Perspective

# Enable perspective for player entity
grid.set_perspective(player)

# This does two things:
# 1. Sets grid.perspective_enabled = True
# 2. Stores weak_ptr to player entity

# Now grid rendering will use player's gridstate for FOV overlay

See Grid-Rendering-Pipeline Stage 4 for overlay rendering details.

Updating Entity Gridstate

After computing FOV, update entity's gridstate:

def update_player_fov():
    """Update player FOV and gridstate"""
    # Compute FOV
    visible_cells = grid.compute_fov(player.x, player.y, radius=10)
    
    # Update gridstate
    for x, y, visible, discovered in visible_cells:
        idx = y * grid.grid_size[0] + x
        player.gridstate[idx].visible = visible
        player.gridstate[idx].discovered = discovered

# Call every time player moves
mcrfpy.setTimer("player_fov", update_player_fov, 100)

Note: This is a manual process currently. Issue #64 may add automatic gridstate updates.

Common Patterns

Opening a Door

def open_door(door_x, door_y):
    """Open door at position, update world state"""
    cell = grid.at((door_x, door_y))
    
    # Update visual
    cell.tilesprite = OPEN_DOOR_SPRITE
    cell.color = (200, 200, 200, 255)
    
    # Update world state
    cell.walkable = True
    cell.transparent = True
    
    # Sync to TCOD (required!)
    grid.sync_tcod_cell(door_x, door_y)
    
    # Recompute FOV if player nearby
    if distance(door_x, door_y, player.x, player.y) < 15:
        update_player_fov()

Dynamic Obstacle

def boulder_falls(x, y):
    """Boulder falls, blocking cell"""
    cell = grid.at((x, y))
    
    # Visual update
    cell.tilesprite = BOULDER_SPRITE
    
    # Block movement and sight
    cell.walkable = False
    cell.transparent = False
    
    # Sync to TCOD
    grid.sync_tcod_cell(x, y)
    
    # Invalidate any paths going through this cell
    for entity in entities:
        if entity.path and (x, y) in entity.path:
            entity.path = None  # Force recompute

Chase AI with Dijkstra

class ChaseAI:
    """AI that chases player using Dijkstra maps"""
    def __init__(self, grid, player):
        self.grid = grid
        self.player = player
        self.dijkstra_dirty = True
    
    def update(self):
        # Recompute Dijkstra map if player moved
        if self.dijkstra_dirty:
            self.grid.compute_dijkstra(self.player.x, self.player.y)
            self.dijkstra_dirty = False
        
        # Move all enemies toward player
        for enemy in enemies:
            path = self.grid.get_dijkstra_path(enemy.x, enemy.y, max_length=1)
            if path:
                next_x, next_y = path[0]
                enemy.move_to(next_x, next_y)
    
    def on_player_move(self):
        self.dijkstra_dirty = True

ai = ChaseAI(grid, player)
mcrfpy.setTimer("ai", lambda ms: ai.update(), 200)  # Update 5x per second

Performance Considerations

FOV Computation Cost

Grid Size	Radius	Time (FOV_BASIC)
50x50	10	~0.5ms
100x100	15	~1.5ms
200x200	20	~4ms

Optimization:

Only compute FOV when entity moves
Use smaller radius when possible
Cache results for stationary entities

Pathfinding Cost

Grid Size	Path Length	Time (A*)
50x50	20 cells	~0.3ms
100x100	50 cells	~1.2ms
200x200	100 cells	~5ms

Optimization:

Limit pathfinding distance for distant targets
Use Dijkstra maps for many entities with same goal
Cache paths and only recompute when grid changes

Sync Cost

syncTCODMap(): O(grid_x * grid_y) - use sparingly
syncTCODMapCell(): O(1) - use freely

Best Practice:

# BAD: Full sync after every cell change
for x in range(100):
    for y in range(100):
        grid.at((x, y)).walkable = compute_walkable(x, y)
        grid.sync_tcod_map()  # O(n²) per cell = O(n⁴) total!

# GOOD: Bulk changes then single sync
for x in range(100):
    for y in range(100):
        grid.at((x, y)).walkable = compute_walkable(x, y)
grid.sync_tcod_map()  # O(n²) once

Troubleshooting

Issue: Pathfinding Returns Empty Path

Causes:

Target is unreachable (blocked by walls)
TCODMap not synchronized after cell changes
Start or end position is non-walkable

Debug:

path = grid.find_path(x1, y1, x2, y2)
if not path:
    # Check walkability
    print(f"Start walkable: {grid.at((x1, y1)).walkable}")
    print(f"End walkable: {grid.at((x2, y2)).walkable}")
    
    # Try computing FOV to see what's reachable
    visible = grid.compute_fov(x1, y1, radius=50)
    if (x2, y2) not in [(x, y) for x, y, _, _ in visible]:
        print("Target not reachable from start!")

Issue: FOV Doesn't Match Visual

Cause: TCODMap transparent property not synced with cell visual.

Fix:

# After changing cell visual
cell = grid.at((x, y))
cell.tilesprite = WALL_SPRITE
cell.transparent = False  # Important!
grid.sync_tcod_cell(x, y)

Issue: Entity Can't See Through Glass

Cause: Glass cells have transparent = False.

Fix:

# Glass cell setup
glass_cell = grid.at((x, y))
glass_cell.walkable = False  # Can't walk through
glass_cell.transparent = True  # CAN see through
grid.sync_tcod_cell(x, y)

API Reference

See docs/api_reference_dynamic.html for complete TCOD API.

FOV Methods:

grid.compute_fov(x, y, radius=0, light_walls=True, algorithm=FOV_BASIC) → List[(x, y, visible, discovered)]
grid.is_in_fov(x, y) → bool

Pathfinding Methods:

grid.find_path(x1, y1, x2, y2, diagonal_cost=1.41) → List[(x, y)]
grid.compute_dijkstra(root_x, root_y, diagonal_cost=1.41) → None
grid.get_dijkstra_path(from_x, from_y, max_length=0) → List[(x, y)]

Sync Methods:

grid.sync_tcod_map() → None (sync entire grid)
grid.sync_tcod_cell(x, y) → None (sync single cell)

Cell Properties:

cell.walkable - Boolean, affects pathfinding
cell.transparent - Boolean, affects FOV

Navigation:

Grid-System - Parent page
AI-and-Pathfinding - Using FOV and pathfinding for game AI
Grid-Rendering-Pipeline - FOV overlay rendering
Entity-Management - Entity gridstate and perspective