Skip to main content

Map Utilities

Version History​

Build VersionChange DateChange TypeDescription
6760422025-06-21stableCurrent version

Overview​

The maputil.lua script provides essential utilities for working with map topology, including pathfinding operations, node manipulation, graph reconstruction, and visualization tools. These functions are used for world generation analysis, debugging, and runtime pathfinding operations.

Usage Example​

-- Find the closest node to player
local closest_node = GetClosestNodeToPlayer()
print("Player is near node:", closest_node.id)

-- Show area around player
ShowClosestNodeToPlayer()

-- Create a convex hull from points
local points = {{0,0}, {1,0}, {1,1}, {0,1}}
local hull = convexHull(points)

Node Finding Functions​

GetClosestNode(x, y)​

Status: stable

Description: Finds the closest topology node to the specified world coordinates.

Parameters:

  • x (number): World X coordinate
  • y (number): World Y coordinate (Z coordinate in 3D space)

Returns:

  • (table): The closest topology node, or nil if no valid nodes exist

Example:

-- Find closest node to a specific position
local node = GetClosestNode(100, 200)
if node then
    print("Found node at:", node.x, node.y)
    print("Node has", #node.neighbours, "neighbours")
end

GetClosestNodeToPlayer()​

Status: stable

Description: Finds the closest topology node to the current player's position.

Returns:

  • (table): The closest topology node to the player

Example:

local player_node = GetClosestNodeToPlayer()
if player_node then
    print("Player is in node:", player_node.id)
    print("Node center:", player_node.x, player_node.y)
end

ShowClosestNodeToPlayer()​

Status: stable

Description: Reveals the closest node to the player on the minimap for debugging purposes.

Example:

-- Debug: Show player's current node on minimap
ShowClosestNodeToPlayer()

Geometry Functions​

cross(o, a, b)​

Status: stable

Description: Calculates the cross product of vectors for geometric calculations.

Parameters:

  • o (table): Origin point {x, y}
  • a (table): First point {x, y}
  • b (table): Second point {x, y}

Returns:

  • (number): Cross product value

convexHull(points)​

Status: stable

Description: Computes the convex hull of a set of 2D points using Andrew's algorithm.

Parameters:

  • points (table): Array of point coordinates {{x1, y1}, {x2, y2}, ...}

Returns:

  • (table): Array of points forming the convex hull

Example:

-- Create convex hull from a set of points
local points = {
    {0, 0}, {2, 0}, {1, 1}, {2, 2}, {0, 2}
}
local hull = convexHull(points)

-- Hull will contain the outer boundary points
for i, point in ipairs(hull) do
    print("Hull point", i, ":", point[1], point[2])
end

Graph Manipulation Functions​

GrabSubGraphAroundNode(node, numnodes)​

Status: stable

Description: Extracts a connected subgraph around a starting node by randomly walking through neighboring nodes.

Parameters:

  • node (table): Starting topology node
  • numnodes (number): Number of nodes to include in the subgraph

Returns:

  • (table): Array of selected nodes forming the subgraph

Example:

-- Get a subgraph of 10 nodes around the player
local start_node = GetClosestNodeToPlayer()
local subgraph = GrabSubGraphAroundNode(start_node, 10)

print("Selected", #subgraph, "nodes in subgraph")
for i, node in ipairs(subgraph) do
    print("Node", i, "at", node.x, node.y)
end

PlayerSub(count)​

Status: stable

Description: Creates a subgraph around the player's position and visualizes its convex hull on the minimap.

Parameters:

  • count (number): Number of nodes to include (default: 5)

Example:

-- Visualize a 7-node subgraph around player
PlayerSub(7)

Map Visualization Functions​

MapHideAll()​

Status: stable

Description: Clears all revealed areas from the minimap.

Example:

-- Reset minimap to unexplored state
MapHideAll()

DrawWalkableGrid(graph)​

Status: stable

Description: Creates debug visualization showing walkable connections between topology nodes.

Parameters:

  • graph (table): Optional topology graph (uses TheWorld.topology by default)

Example:

-- Show debug visualization of walkable areas
DrawWalkableGrid()

-- Use custom graph
DrawWalkableGrid(custom_topology)

ShowWalkableGrid(graph)​

Status: stable

Description: Reveals walkable connections on the minimap by showing traversable paths between nodes.

Parameters:

  • graph (table): Optional topology graph (uses TheWorld.topology by default)

Example:

-- Reveal all walkable paths on minimap
ShowWalkableGrid()

Topology Reconstruction​

ReconstructTopology(graph)​

Status: stable

Description: Rebuilds the topology graph by validating node connections and removing invalid pathways. This is a complex operation that reconstructs the entire pathfinding graph.

Parameters:

  • graph (table): Optional topology graph (uses TheWorld.topology by default)

Process:

  1. Point Flattening: Consolidates duplicate vertices
  2. Edge Sorting: Identifies shared edges between nodes
  3. Node Connection: Maps nodes to their shared edges
  4. Path Validation: Checks if connections are actually traversable
  5. Neighbor Assignment: Updates node neighbor lists

Example:

-- Rebuild topology after world changes
ReconstructTopology()

-- Rebuild custom topology
ReconstructTopology(custom_graph)

Performance Note: This is an expensive operation that should only be called when the world topology has been significantly modified.

Internal Utility Functions​

RemoveEdge(nodes, edgeIndex)​

Status: stable

Description: Internal function that removes an edge index from all nodes' valid edge lists.

Parameters:

  • nodes (table): Array of topology nodes
  • edgeIndex (number): Edge index to remove

Data Structures​

Topology Node Structure​

local node = {
    id = 1,                    -- Node identifier
    x = 100,                   -- World X coordinate
    y = 200,                   -- World Y coordinate (Z in 3D)
    poly = {{x1,y1}, {x2,y2}}, -- Polygon vertices
    neighbours = {2, 3, 5},    -- Connected node IDs
    validedges = {1, 4, 7},    -- Valid edge indices
    -- Additional node properties...
}

Graph Structure​

local topology = {
    nodes = {},              -- Array of topology nodes
    flattenedPoints = {},    -- Consolidated vertex list
    flattenedEdges = {},     -- Edge definitions {{p1, p2}, ...}
    edgeToNodes = {},        -- Edge to node mapping
    -- Additional graph properties...
}

Usage Patterns​

Pathfinding Analysis​

-- Analyze connectivity around player
local player_node = GetClosestNodeToPlayer()
print("Player has", #player_node.neighbours, "paths available")

-- Check if two positions are in connected nodes
local node1 = GetClosestNode(x1, y1)
local node2 = GetClosestNode(x2, y2)
local connected = table.contains(node1.neighbours, node2.id)

Map Generation Debugging​

-- Visualize topology structure
DrawWalkableGrid()
ShowWalkableGrid()

-- Test subgraph extraction
local test_node = GetClosestNodeToPlayer()
local subgraph = GrabSubGraphAroundNode(test_node, 8)
PlayerSub(8) -- Visualize the result

World Modification​

-- After making world changes that affect pathfinding
ReconstructTopology()

-- Verify the reconstruction worked
local node = GetClosestNodeToPlayer()
print("Node has", #node.neighbours, "valid connections")

Performance Considerations​

  • GetClosestNode: O(n) operation that checks all nodes
  • convexHull: O(n log n) due to sorting step
  • ReconstructTopology: Expensive O(n²) operation for large graphs
  • GrabSubGraphAroundNode: O(k) where k is the requested node count