5 ms·

(author here) I wrote most of these notes in 1997 while working on a game. Little did I realize that it'd be one of my most popular web pages. The diagrams ar

by amitp 12y ago

(author here) I wrote most of these notes in 1997 while working on a game. Little did I realize that it'd be one of my most popular web pages. The diagrams are colorful but I don't like them (http://simblob.blogspot.com/2013/12/diagrams-on-my-pathfinding-pages.html http://simblob.blogspot.com/2013/12/diagrams-on-my-pathfindi...) so I'm now making new interactive diagrams, starting with breadth first search (http://www.redblobgames.com/pathfinding/tower-defense/ http://www.redblobgames.com/pathfinding/tower-defense/). While writing that page, I realized that I need to explain graphs (http://www.redblobgames.com/pathfinding/grids/graphs.html http://www.redblobgames.com/pathfinding/grids/graphs.html) (many game developers don't know graph theory) and suggest optimizations for grids (http://www.redblobgames.com/pathfinding/grids/algorithms.html http://www.redblobgames.com/pathfinding/grids/algorithms.htm...) (a common use case, with interesting variants of A* like Jump Point Search). I'm also unhappy with the overall structure and navigation so I have a rough plan for how to organize the new pages (https://twitter.com/redblobgames/status/410182845777195008/photo/1 https://twitter.com/redblobgames/status/410182845777195008/p...). I'm taking it one page at a time instead of trying to do it all at once. Feedback appreciated!

agersant 12y ago
Your page was a great source of knowledge and motivation for me when I was learning the ropes of game development (some ~12 years ago). Thanks for all the great work!
vowelless 12y ago
I just want to say thank you! I have that page burned in my memory. I relied on it heavily when I first encountered A* many years ago in undergrad. I think you have changed the design of the page because I don't remember so much red!
- amitp 12y ago
  You're welcome! I do change the design every few years. The earliest one on Wayback Machine is https://web.archive.org/web/19981202094104/http://theory.stanford.edu/~amitp/GameProgramming/ https://web.archive.org/web/19981202094104/http://theory.sta...
eliben 12y ago
Loved your articles back in the day :-) The new animated diagrams are really cool. Can you describe in a few words how you create them?
- amitp 12y ago
  Thanks! I use d3.js + SVG for most of the interactive ones. SVG makes it easy for me to attach mouse events to the elements in the diagram, and d3.js makes it easy for me to create, remove, and animate the elements individually. For the tower defense (breadth first search) page, I have three elements: 1. The graph (square grid for now but I'll make other types) — nodes and edges and edge weights 2. The search algorithm (breadth first search for now) — visited, open, costs, parent pointers. 3. The SVG visualization — a polygon for each node colored by its search state, and overlays for text or arrows When the slider moves, I rewind or advance the search algorithm, which tells me which nodes have changed. I then update those nodes in the diagram. I considered running search once and recording a trace, but it turned out the performance bottleneck was the SVG, not the algorithm, so I didn't bother. It's fast enough to re-run at each step.
  - eliben 12y ago
    Cool, thanks for the details.
samstave 12y ago
How would you deal with an obstruction in the center of the U obstacle that occludes an alternate path through the U to the goal?
sesqu 12y ago
FWIW, I liked the colors, but totally misinterpreted them (I assumed the color represented a single value on a gradient, rather than two channels), and I almost missed the "next page" link at the bottom I also thought it would be better to have the starting point inside the convex hull or the ending point higher behind it, so that the algorithm would look further than 1 square in the counter-heuristic directions. As it is, the heuristic was exactly correct about the length of the final path, it just happened to start searching to the right instead of starting straight down.

by amitp 12y ago

agersant 12y ago

Your page was a great source of knowledge and motivation for me when I was learning the ropes of game development (some ~12 years ago). Thanks for all the great work!

vowelless 12y ago

I just want to say thank you! I have that page burned in my memory. I relied on it heavily when I first encountered A* many years ago in undergrad. I think you have changed the design of the page because I don't remember so much red!

amitp 12y ago
You're welcome! I do change the design every few years. The earliest one on Wayback Machine is https://web.archive.org/web/19981202094104/http://theory.stanford.edu/~amitp/GameProgramming/ https://web.archive.org/web/19981202094104/http://theory.sta...

eliben 12y ago

Loved your articles back in the day :-) The new animated diagrams are really cool. Can you describe in a few words how you create them?

amitp 12y ago
Thanks! I use d3.js + SVG for most of the interactive ones. SVG makes it easy for me to attach mouse events to the elements in the diagram, and d3.js makes it easy for me to create, remove, and animate the elements individually. For the tower defense (breadth first search) page, I have three elements: 1. The graph (square grid for now but I'll make other types) — nodes and edges and edge weights 2. The search algorithm (breadth first search for now) — visited, open, costs, parent pointers. 3. The SVG visualization — a polygon for each node colored by its search state, and overlays for text or arrows When the slider moves, I rewind or advance the search algorithm, which tells me which nodes have changed. I then update those nodes in the diagram. I considered running search once and recording a trace, but it turned out the performance bottleneck was the SVG, not the algorithm, so I didn't bother. It's fast enough to re-run at each step.
- eliben 12y ago
  Cool, thanks for the details.

samstave 12y ago

How would you deal with an obstruction in the center of the U obstacle that occludes an alternate path through the U to the goal?

sesqu 12y ago

FWIW, I liked the colors, but totally misinterpreted them (I assumed the color represented a single value on a gradient, rather than two channels), and I almost missed the "next page" link at the bottom I also thought it would be better to have the starting point inside the convex hull or the ending point higher behind it, so that the algorithm would look further than 1 square in the counter-heuristic directions. As it is, the heuristic was exactly correct about the length of the final path, it just happened to start searching to the right instead of starting straight down.