Please turn JavaScript on to use this site.
Worlds
Minds
Users
Uploads
JS code
Search
Worlds
Minds
Users
Uploads
JS code
Intro
Introduction
Features
Definitions
Principles
The AI model
Teaching
Register a class
Learn
Getting started
P5 tutorial
Three.js tutorial
Coding course
Coding course II
Coding for kids
WebGL course
AI exercises
Browse
Starter Worlds
Editor's Choice
Showcase Worlds
Multi-user Worlds
Random Worlds
Advanced search
Docs
Docs
API docs
Register
Register
Forgot password
Login
Step 4. A
*
search
This program implements the
A
*
algorithm
and allows us modify it.
Video
World
A star
"A Star" algorithm to find shortest path through maze.
Clone and Edit
Notes
A
*
seeks a goal using a heuristic
estimate
of distance from goal.
It will find the shortest (or joint shortest) path.
Goal here: Find optimal path from top LHS corner to bottom RHS corner.
Reload for a new problem.
Sometimes there is no path.
Credits
This is a modified port of
05_astar
from
AI course
by Daniel Shiffman.
See his videos parts
one
and
two
and
three
.
Modified to give randomised world size and randomised wall density.
Modified to give a switch to say if diagonal moves are allowed or not.
Modified to use different heuristics for diagonal v. non-diagonal.
Look at code
See
code
.
Two versions: Are diagonal moves allowed or not? See boolean "diagonal".
Heuristic for World with diagonal moves allowed:
2D distance to the goal
. This is always optimistic.
Heuristic for World with no diagonal moves allowed:
Distance across plus distance down
. This is always optimistic.
Colours:
Black - wall
Green - open list - squares known but not yet checked
Pink - closed list - squares examined
Dark red - a joint shortest path
Exercise
Clone and Edit the World.
Change the various customisable values.
Change the speed. See the "frameRate" line.
Change open and closed colours to white.
Change it to no walls at all, diagonal.
Change it to no walls, no diagonal.
Question: Why does it look so strange? Is it really finding the shortest path?
Change the code to use the other heuristic.
Previous
Next: Step 5 of 9
Tweet this step: