en.unionpedia.org

Pathfinding, the Glossary

Index Pathfinding

Pathfinding or pathing is the search, by a computer application, for the shortest route between two points.[1]

Table of Contents

  1. 39 relations: A* search algorithm, Algorithm, Any-angle path planning, Bellman–Ford algorithm, Breadth-first search, Brute-force search, Cellular automaton, Chebyshev distance, Chris Crawford (game designer), Cluster analysis, Collaborative diffusion, Contraction hierarchies, CPU time, D*, Depth-first search, Dijkstra's algorithm, Dynamic programming, Embarrassingly parallel, Euclidean distance, Glossary of graph theory, Graph (abstract data type), Graph theory, Guided local search, Heuristic (computer science), Incremental heuristic search, Intelligent agent, Maze-solving algorithm, Mini-map, Motion planning, Navigation mesh, Node (computer science), Plane (mathematics), Shortest path problem, Stanford Research Institute Problem Solver, Tanktics: Computer Game of Armored Combat on the Eastern Front, Transportation planning, Travelling salesman problem, Vertex (graph theory), Video game industry.

  2. Edsger W. Dijkstra
  3. Routing algorithms
  4. Scoutcraft

A* search algorithm

A* (pronounced "A-star") is a graph traversal and pathfinding algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Pathfinding and a* search algorithm are game artificial intelligence and Routing algorithms.

See Pathfinding and A* search algorithm

Algorithm

In mathematics and computer science, an algorithm is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

See Pathfinding and Algorithm

Any-angle path planning

Any-angle path planning algorithms are pathfinding algorithms that search for a Euclidean shortest path between two points on a grid map while allowing the turns in the path to have any angle.

See Pathfinding and Any-angle path planning

Bellman–Ford algorithm

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.

See Pathfinding and Bellman–Ford algorithm

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property.

See Pathfinding and Breadth-first search

In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically checking all possible candidates for whether or not each candidate satisfies the problem's statement.

See Pathfinding and Brute-force search

Cellular automaton

A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory.

See Pathfinding and Cellular automaton

Chebyshev distance

In mathematics, Chebyshev distance (or Tchebychev distance), maximum metric, or L∞ metric is a metric defined on a real coordinate space where the distance between two points is the greatest of their differences along any coordinate dimension.

See Pathfinding and Chebyshev distance

Chris Crawford (game designer)

Christopher Crawford (born June 1, 1950) is an American video game designer and writer.

See Pathfinding and Chris Crawford (game designer)

Cluster analysis

Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some specific sense defined by the analyst) to each other than to those in other groups (clusters).

See Pathfinding and Cluster analysis

Collaborative diffusion

Collaborative Diffusion is a type of pathfinding algorithm which uses the concept of antiobjects, objects within a computer program that function opposite to what would be conventionally expected.

See Pathfinding and Collaborative diffusion

Contraction hierarchies

In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest-path in a graph. Pathfinding and contraction hierarchies are Routing algorithms.

See Pathfinding and Contraction hierarchies

CPU time

CPU time (or process time) is the amount of time for which a central processing unit (CPU) was used for processing instructions of a computer program or operating system, as opposed to elapsed time, which includes for example, waiting for input/output (I/O) operations or entering low-power (idle) mode.

See Pathfinding and CPU time

D*

D* (pronounced "D star") is any one of the following three related incremental search algorithms.

See Pathfinding and D*

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.

See Pathfinding and Depth-first search

Dijkstra's algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. Pathfinding and Dijkstra's algorithm are Edsger W. Dijkstra and Routing algorithms.

See Pathfinding and Dijkstra's algorithm

Dynamic programming

Dynamic programming is both a mathematical optimization method and an algorithmic paradigm.

See Pathfinding and Dynamic programming

Embarrassingly parallel

In parallel computing, an embarrassingly parallel workload or problem (also called embarrassingly parallelizable, perfectly parallel, delightfully parallel or pleasingly parallel) is one where little or no effort is needed to split the problem into a number of parallel tasks.

See Pathfinding and Embarrassingly parallel

Euclidean distance

In mathematics, the Euclidean distance between two points in Euclidean space is the length of the line segment between them.

See Pathfinding and Euclidean distance

Glossary of graph theory

This is a glossary of graph theory.

See Pathfinding and Glossary of graph theory

Graph (abstract data type)

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics.

See Pathfinding and Graph (abstract data type)

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

See Pathfinding and Graph theory

Guided local search is a metaheuristic search method.

See Pathfinding and Guided local search

Heuristic (computer science)

In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution, or when classic methods fail to find any exact solution in a search space.

See Pathfinding and Heuristic (computer science)

Incremental heuristic search algorithms combine both incremental and heuristic search to speed up searches of sequences of similar search problems, which is important in domains that are only incompletely known or change dynamically.

See Pathfinding and Incremental heuristic search

Intelligent agent

In intelligence and artificial intelligence, an intelligent agent (IA) is an agent acting in an intelligent manner.

See Pathfinding and Intelligent agent

Maze-solving algorithm

A maze-solving algorithm is an automated method for solving a maze.

See Pathfinding and Maze-solving algorithm

Mini-map

A mini-map or minimap is a miniature map HUD element that is often placed at a screen corner in video games to help players in orienting themselves within the game world.

See Pathfinding and Mini-map

Motion planning

Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination.

See Pathfinding and Motion planning

A navigation mesh, or navmesh, is an abstract data structure used in artificial intelligence applications to aid agents in pathfinding through complicated spaces.

See Pathfinding and Navigation mesh

Node (computer science)

A node is a basic unit of a data structure, such as a linked list or tree data structure.

See Pathfinding and Node (computer science)

Plane (mathematics)

In mathematics, a plane is a two-dimensional space or flat surface that extends indefinitely.

See Pathfinding and Plane (mathematics)

Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. Pathfinding and shortest path problem are Edsger W. Dijkstra.

See Pathfinding and Shortest path problem

Stanford Research Institute Problem Solver

The Stanford Research Institute Problem Solver, known by its acronym STRIPS, is an automated planner developed by Richard Fikes and Nils Nilsson in 1971 at SRI International.

See Pathfinding and Stanford Research Institute Problem Solver

Tanktics: Computer Game of Armored Combat on the Eastern Front

Tanktics: Computer Game of Armored Combat on the Eastern Front is a 1976 two-player tank battle computer wargame by Chris Crawford.

See Pathfinding and Tanktics: Computer Game of Armored Combat on the Eastern Front

Transportation planning

Transportation planning is the process of defining future policies, goals, investments, and spatial planning designs to prepare for future needs to move people and goods to destinations.

See Pathfinding and Transportation planning

Travelling salesman problem

The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

See Pathfinding and Travelling salesman problem

Vertex (graph theory)

In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).

See Pathfinding and Vertex (graph theory)

Video game industry

The video game industry is the tertiary and quaternary sectors of the entertainment industry that specialize in the development, marketing, distribution, monetization and consumer feedback of video games.

See Pathfinding and Video game industry

See also

Edsger W. Dijkstra

Routing algorithms

Scoutcraft

References

[1] https://en.wikipedia.org/wiki/Pathfinding

Also known as Hierarchical path finding, List of algorithms used in pathfinding, List of pathfinding algorithms, Path finding, Path planning algorithm, Pathfinding algorithm, Pathing, Pathplanning, Route optimization.