Please enable JavaScript.
Coggle requires JavaScript to display documents.
Goal-based agents - pathfinding - Coggle Diagram
Goal-based agents - pathfinding
Definition of Path Finding
A goal-based agent in pathfinding is a program or system designed to find the best route from a starting point to a desired destination within a given environment.
FSM (Finite State Machine)
A Finite State Machine (FSM) is like a flowchart showing different states a system can be in, with rules dictating when it moves from one state to another.
Applications
Coin-Operated turnstile
States : Locked, Unlocked
Traffic Lights
State : Red ,Green ,Yellow
Locker State : Multiple "locked" states, one "unlocked" state
Types
Mealy state machine
Moore state machine
Network
: A network is simply a collection of connected object
Network Types
Directed
Connections between this nodes are directed
Weighted
Directed or undirected edges can also have weight or a quantitative value associated with them.
Undirected
The relationship between the nodes is a simple connection. Nodes are not directed to a another.
Examples
Topography
Tile based games
Website index
A electronic circuit diagram
Searching Algorithms
Searching Algorithms
A* Search
An Improvement to the current algorithms.
Use heuristic to find the optimal solution
Requires more memory compared to other algorithms
Impractical for large data sets
BFS (Breadth First Search)
Visit all the nodes around starting from a point
Slower than BFS
Prevent revisiting visited nodes
Guarantees shortest path to the target
Can be used to determine the shortest path and minimum spanning tree.
DFS (Depth First Search)
Explore each node only once
Follow each node to its limit
Reverse when at dead end
Can be used to the find the paths between to vertices.
Can also be used to detect cycles in the graph.
Web Links
http://mathworld.wolfram.com/TravelingSalesmanProblem.html
http://www.wired.com/2013/01/traveling-salesman-problem/all/
http://www.kongregate.com/games/WhereIs_Treasure/city-traffic-simulator
http://qiao.github.io/PathFinding.js/visual/
Digraph (Directed Graph)
Edges are represented as links between nodes with optional key/value attributes
Stores noes and edges with optional data, or attributes
Hold directed edges. Self loop are allowed but multiple (parallel) edges are not.
Edges have different costs Ex :Cannot go backwards, uphill or downhill
