astar_example.cc File Reference

A* shortest path in Aleph-w (grid graph, heuristics, and comparison with Dijkstra). More...

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <chrono>
#include <limits>
#include <tpl_graph.H>
#include <AStar.H>
#include <Dijkstra.H>

Include dependency graph for astar_example.cc:

Go to the source code of this file.

Classes
struct	GridCell
	Node info containing 2D coordinates. More...
struct	GridDistance
	Distance functor that reads arc weights. More...
struct	EuclideanHeuristic
	Euclidean distance heuristic. More...
struct	ManhattanHeuristic
	Manhattan distance heuristic. More...

Typedefs
using	GridNode = Graph_Node< GridCell >
using	GridArc = Graph_Arc< double >
using	GridGraph = List_Graph< GridNode, GridArc >

Functions
GridGraph	create_grid_graph (int width, int height, bool diagonal, vector< GridGraph::Node * > &nodes)
	Creates a 2D grid graph.
void	print_grid_with_path (int width, int height, const vector< GridGraph::Node * > &nodes, GridGraph::Node *start, GridGraph::Node *end, const Path< GridGraph > &path)
	Prints the grid with the path highlighted.
template<typename Func >
double	measure_time_ms (Func &&f)
int	main ()

Detailed Description

A* shortest path in Aleph-w (grid graph, heuristics, and comparison with Dijkstra).

Overview

This example demonstrates Aleph-w's A* implementation (AStar.H) on a 2D grid. A* is a best-first shortest-path algorithm that uses a heuristic h(n) to guide the search, typically expanding far fewer nodes than Dijkstra when the heuristic is informative.

It also compares A* with Dijkstra on the same grid setup.

Data model used by this example

• Graph type: GridGraph = List_Graph<Graph_Node<GridCell>, Graph_Arc<double>>
• Node info: GridCell { x, y, blocked }
• Arc info: edge cost (double)

The helper create_grid_graph(width, height, diagonal, nodes) builds a regular grid and optionally adds diagonal connections (8-connected vs 4-connected).

Usage

./astar_example

This example has no command-line options; the demo scenarios are hard-coded.

Algorithms

A* uses:

• g(n): cost from start to n
• h(n): heuristic estimate from n to goal
• f(n) = g(n) + h(n) to prioritize expansions

Two heuristics are shown:

• Euclidean (sqrt(dx^2 + dy^2)): admissible when diagonal moves are allowed.
• Manhattan (|dx| + |dy|): admissible for 4-connected grids.

A* is guaranteed to find an optimal path when h is admissible (never overestimates) and typically behaves best when it is also consistent.

Complexity

Let V be the number of nodes and E the number of edges.

• Worst-case time is similar to Dijkstra: O((V + E) log V) (priority queue).
• Auxiliary space is O(V).

In practice, a good heuristic can reduce the number of expanded nodes.

Pitfalls and edge cases

• Heuristic quality: a weak heuristic makes A* behave like Dijkstra.
• Heuristic admissibility: if h overestimates, A* may return suboptimal paths.
• Movement model mismatch: use Manhattan for 4-neighbor movement and Euclidean (or octile) when diagonals are allowed.

References / see also

• AStar.H (implementation)
• Dijkstra.H / dijkstra_example.cc (uninformed shortest paths)

Author

Leandro Rabindranath León

Definition in file astar_example.cc.

Typedef Documentation

GridArc

using GridArc = Graph_Arc<double>

Definition at line 140 of file astar_example.cc.

GridGraph

using GridGraph = List_Graph<GridNode, GridArc>

Definition at line 141 of file astar_example.cc.

GridNode

using GridNode = Graph_Node<GridCell>

Definition at line 139 of file astar_example.cc.

Function Documentation

create_grid_graph()

GridGraph create_grid_graph	(	int	width,
		int	height,
		bool	diagonal,
		vector< GridGraph::Node * > &	nodes
	)

Creates a 2D grid graph.

Parameters

width	Grid width (number of columns).
height	Grid height (number of rows).
diagonal	If true, add diagonal connections (8-connected).
nodes	Output vector of node pointers indexed by y*width+x.

Returns

The constructed grid graph.

Definition at line 217 of file astar_example.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), nodes, sqrt(), and y.

Referenced by main().

main()

int main

(

)

Definition at line 347 of file astar_example.cc.

References create_grid_graph(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), HEIGHT, Aleph::maps(), measure_time_ms(), print_grid_with_path(), Aleph::Path< GT >::size(), sqrt(), and WIDTH.

measure_time_ms()

template<typename Func >

double measure_time_ms

(

Func &&

f

)

Definition at line 335 of file astar_example.cc.

Referenced by main().

print_grid_with_path()

void print_grid_with_path	(	int	width,
		int	height,
		const vector< GridGraph::Node * > &	nodes,
		GridGraph::Node *	start,
		GridGraph::Node *	end,
		const Path< GridGraph > &	path
	)

Prints the grid with the path highlighted.

Legend: S = Start E = End

• = Path . = Empty cell

Definition at line 292 of file astar_example.cc.

References GTNodeCommon< NodeInfo >::get_info(), Aleph::Dlink::Iterator::has_curr(), Aleph::maps(), nodes, and y.

Referenced by main().