Pipe connectivity pathfinding

from Red Blob Games

This reddit question made me think about edge-to-edge pathfinding. A* works whenever you can give it “locations” (possibly abstract) and “connections” between locations. For pipe connectivity the locations are tile edges. The connections are whatever you can get to with a straight pipe or a bent pipe.


I’m going to use the tile edge coordinates from here except I’ll use top-left coordinates: tile 0,0 will have 0,0,W on the left and 1,0,W on the right. It will have 0,0,N on the top and 0,1,N on the bottom.


Rules for vertical edge: i,j,W →

  1. i-2,j-1,N [red]
  2. i-2,j+2,N [red]
  3. i+1,j-1,N [red]
  4. i+1,j+2,N [red]
  5. i-5,j,W [blue]
  6. i+5,j,W [blue]

Rules for horizontal edge: i,j,N →

  1. i+2,j+1,W [red]
  2. i+2,j-2,W [red]
  3. i-1,j+1,W [red]
  4. i-1,j-2,W [red]
  5. i,j-5,N [blue]
  6. i,j+5,N [blue]


(implement interactive demo showing connectivity)
1 - draw grid
2 - mark an edge on the grid in a color 
3 - mouse position to closest edge (diamond tile shape)
4 - mouse hover handler to update which edge we're looking at

Demo 2

(implement interactive demo showing pathfinding)
5 - neighbors() function for A* that implements our movement rules, and filters for edges actually on the map
6 - pathfinding code using edge coordinates and neighbors()
7 - mouse drag handler to move start/end point of A*
8 - output drawing code that distinguishes two different types of pipe pieces