 | This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these template messages)
|
Theta* is an any-angle path planning algorithm that is based on the A* search algorithm. It can find near-optimal paths with run times comparable to those of A*. [1]
For the simplest version of Theta*, the main loop is much the same as that of A*. The only difference is the function. Compared to A*, the parent of a node in Theta* does not have to be a neighbor of the node as long as there is a line-of-sight between the two nodes.[ citation needed ]
Adapted from. [2]
functiontheta*(start,goal)// This main loop is the same as A*gScore(start):=0parent(start):=start// Initializing open and closed sets. The open set is initialized // with the start node and an initial costopen:={}open.insert(start,gScore(start)+heuristic(start))// gScore(node) is the current shortest distance from the start node to node// heuristic(node) is the estimated distance of node from the goal node// there are many options for the heuristic such as Euclidean or Manhattan closed:={}whileopenisnotemptys:=open.pop()ifs=goalreturnreconstruct_path(s)closed.push(s)foreachneighborofs// Loop through each immediate neighbor of sifneighbornotinclosedifneighbornotinopen// Initialize values for neighbor if it is // not already in the open listgScore(neighbor):=infinityparent(neighbor):=Nullupdate_vertex(s,neighbor)returnNullfunctionupdate_vertex(s,neighbor)// This part of the algorithm is the main difference between A* and Theta*ifline_of_sight(parent(s),neighbor)// If there is line-of-sight between parent(s) and neighbor// then ignore s and use the path from parent(s) to neighbor ifgScore(parent(s))+c(parent(s),neighbor)<gScore(neighbor)// c(s, neighbor) is the Euclidean distance from s to neighborgScore(neighbor):=gScore(parent(s))+c(parent(s),neighbor)parent(neighbor):=parent(s)ifneighborinopenopen.remove(neighbor)open.insert(neighbor,gScore(neighbor)+heuristic(neighbor))else// If the length of the path from start to s and from s to // neighbor is shorter than the shortest currently known distance// from start to neighbor, then update node with the new distanceifgScore(s)+c(s,neighbor)<gScore(neighbor)gScore(neighbor):=gScore(s)+c(s,neighbor)parent(neighbor):=sifneighborinopenopen.remove(neighbor)open.insert(neighbor,gScore(neighbor)+heuristic(neighbor))functionreconstruct_path(s)total_path={s}// This will recursively reconstruct the path from the goal node // until the start node is reachedifparent(s)!=stotal_path.push(reconstruct_path(parent(s)))elsereturntotal_pathlineOfSight(node1,node2){letx0=node1.x;lety0=node1.y;letx1=node2.x;lety1=node2.y;letdx=abs(x1-x0);letdy=-abs(y1-y0);letsX=-1;letsY=-1;if(x0<x1){sX=1;}if(y0<y1){sY=1;}lete=dx+dy;while(true){letpoint=getNode(x0,y0);if(pointdoesnotexistORpointisnotwalkable){returnfalse;}if(x0==x1ANDy0==y1){returntrue;}lete2=2*e;if(e2>=dy){if(x0==x1){returntrue;}e+=dy;x0+=sX;}if(e2<=dx){if(y0==y1){returntrue;}e+=dx;y0+=sY;}}}The following variants of the algorithm exist:[ citation needed ]
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
Bresenham's line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw line primitives in a bitmap image, as it uses only integer addition, subtraction, and bit shifting, all of which are very cheap operations in historically common computer architectures. It is an incremental error algorithm, and one of the earliest algorithms developed in the field of computer graphics. An extension to the original algorithm called the midpoint circle algorithm may be used for drawing circles.
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.
A* is a graph traversal and pathfinding algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Given a weighted graph, a source node and a goal node, the algorithm finds the shortest path from source to goal.
Best-first search is a class of search algorithms, which explores a graph by expanding the most promising node chosen according to a specified rule.
Xiaolin Wu's line algorithm is an algorithm for line antialiasing.
Perlin noise is a type of gradient noise developed by Ken Perlin in 1983. It has many uses, including but not limited to: procedurally generating terrain, applying pseudo-random changes to a variable, and assisting in the creation of image textures. It is most commonly implemented in two, three, or four dimensions, but can be defined for any number of dimensions.
Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.
Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet. The reason for this approach is that in many cases it is faster: for instance, in a simplified model of search problem complexity in which both searches expand a tree with branching factor b, and the distance from start to goal is d, each of the two searches has complexity O(bd/2) (in Big O notation), and the sum of these two search times is much less than the O(bd) complexity that would result from a single search from the beginning to the goal.
In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes of the input sequence:
In computer graphics, a digital differential analyzer (DDA) is hardware or software used for interpolation of variables over an interval between start and end point. DDAs are used for rasterization of lines, triangles and polygons. They can be extended to non linear functions, such as perspective correct texture mapping, quadratic curves, and traversing voxels.
For digital image processing, the Focus recovery from a defocused image is an ill-posed problem since it loses the component of high frequency. Most of the methods for focus recovery are based on depth estimation theory. The Linear canonical transform (LCT) gives a scalable kernel to fit many well-known optical effects. Using LCTs to approximate an optical system for imaging and inverting this system, theoretically permits recovery of a defocused image.
In the field of mathematical analysis, an interpolation space is a space which lies "in between" two other Banach spaces. The main applications are in Sobolev spaces, where spaces of functions that have a noninteger number of derivatives are interpolated from the spaces of functions with integer number of derivatives.
In Euclidean geometry, the distance from a point to a line is the shortest distance from a given point to any point on an infinite straight line. It is the perpendicular distance of the point to the line, the length of the line segment which joins the point to nearest point on the line. The algebraic expression for calculating it can be derived and expressed in several ways.
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. The result is a path that cuts directly through open areas and has relatively few turns. More traditional pathfinding algorithms such as A* either lack in performance or produce jagged, indirect paths.
In category theory, a branch of mathematics, the exact completion constructs a Barr-exact category from any finitely complete category. It is used to form the effective topos and other realizability toposes.
In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem.
In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.
JMesh is a JSON-based portable and extensible file format for the storage and interchange of unstructured geometric data, including discretized geometries such as triangular and tetrahedral meshes, parametric geometries such as NURBS curves and surfaces, and constructive geometries such as constructive solid geometry (CGS) of shape primitives and meshes. Built upon the JData specification, a JMesh file utilizes the JSON and Universal Binary JSON (UBJSON) constructs to serialize and encode geometric data structures, therefore, it can be directly processed by most existing JSON and UBJSON parsers. The JMesh specification defines a list of JSON-compatible constructs to encode geometric data, including N-dimensional (ND) vertices, curves, surfaces, solid elements, shape primitives, their interactions and spatial relations, together with their associated properties, such as numerical values, colors, normals, materials, textures and other properties related to graphics data manipulation, 3-D fabrication, computer graphics rendering and animations.