This is similar to the algorithm currently used in V to connect the dungeon, with some modifications.

You start with a set of room centers and a set of centers for special rooms. Dungeon generation is accomplished in two parts.

1. all the simple rooms are connected (efficiently) with angband style tunnels.
2. all the special rooms (vaults, templated rooms) are connected through A* connection on a predetermined noise grid.

The two routines only differ in tunnel style, the main steps for connection are the same.

1. Make a color map where each disconnected region gets its own color.
2. Pick two random regions.
3. Pick two close points A and B in these regions.
4. Find a tunnel path from A to B stopping if we hit a different unconnected region in the way. This part can be either angband style or A* style.
5. Actually make the tunnel, setting pierceable cells and junction squares as needed.
6. Coalesce the two now connected regions and the tunnel into a single entry in the colorMap, reducing the number of unconnected regions by one.
7. Repeat from step 2 until only one region is left.

Angband style tunnels are used to connect simple rooms. A room is simple if it is surrounded by pierceable walls. This covers almost every room except for vaults and templated rooms. (Note: tunnels must be flanked by pierceable walls also for this to work). The tunnels are made in the following manner.

1. Start at A and head in the direction of B
2. At each step calculate the possibility for a random turn
3. If you hit an obstacle, use the marching squares algorithm to path around the edge of the obstacle, peeling off when appropriate
4. Stop when you hit a pierceable square
5. If the pierceable square is not connected to a new region (the tunnel intersected itself) discard and try again.
6. If you hit the boundary discard and try again

Angband style tunnels will fail occasionally, and it's possible that they will not be able to connect every simple room if the dungeon is very dense with a lot of obstacles in it. Nevertheless, the tunnel pathing is very quick (scales linearly with A to B distance).

Angband style tunnels currently differ from the normal style in that they are much more efficient. There are no tunnels that leave a room, turn around, and intersect it again. These tunnels can be added afterwards for flavor purposes.

The other tunnel type is the A* algorithm, it is described here http://en.wikipedia.org/wiki/A*_search_algorithm in detail, and is implemented very similar to the wiki file. But to be pedantic here is the rough outline.

Given start point A and target B and a map of costs do the following:

1. Add A to the active heap.
2. Pop the top point in the heap (at the beginning this is A)
3. Add all points adjacent to A into an active heap and a dictionary of tried points if they are cheaper than any predetermined paths to that point.

• the heap is sorted by the actual cost from A to the point + an estimated cost
• heap data include the point, the previous point, and the actual cost.
• tried points is sorted by point location and includes the previous point and the actual cost

1. repeat from 2 until the point B is reached
2. reconstruct the tunnel building backwards from B until we reach A