Method findPath

internal/mapper/mapper.path.go:102–194

FindPath returns the sequence of ExitName/RoomID steps from startRoom to goalRoom.

(startRoom, goalRoom int)

// FindPath returns the sequence of ExitName/RoomID steps from startRoom to goalRoom.
func (r *mapper) findPath(startRoom, goalRoom int) ([]pathStep, error) {

	if startRoom == goalRoom {
		return nil, ErrPathDestMatch
	}

	// sanity check
	if _, ok := r.crawledRooms[startRoom]; !ok {
		return nil, ErrRoomNotFound
	}
	if _, ok := r.crawledRooms[goalRoom]; !ok {
		return nil, ErrRoomNotFound
	}

	// cameFrom holds, for each room, how we got there.
	cameFrom := make(map[int]prevInfo, len(r.crawledRooms))

	// gScore: cost from start to here; fScore = gScore + heuristic
	gScore := make(map[int]float64, len(r.crawledRooms))
	fScore := make(map[int]float64, len(r.crawledRooms))
	for id := range r.crawledRooms {
		gScore[id] = math.Inf(1)
		fScore[id] = math.Inf(1)
	}
	gScore[startRoom] = 0
	fScore[startRoom] = r.heuristic(startRoom, goalRoom)

	// open set as a priority queue
	openSet := make(priorityQueue, 0, len(r.crawledRooms))
	heap.Init(&openSet)
	heap.Push(&openSet, &nodeRecord{roomId: startRoom, fScore: fScore[startRoom]})
	inOpen := map[int]*nodeRecord{startRoom: openSet[0]}

	for openSet.Len() > 0 {
		current := heap.Pop(&openSet).(*nodeRecord)
		delete(inOpen, current.roomId)

		// reached goal!
		if current.roomId == goalRoom {
			// reconstruct path
			var path []pathStep
			cur := goalRoom
			for cur != startRoom {
				info := cameFrom[cur]

				// record the exit name and the room we arrived in
				path = append(path, pathStep{exitName: info.viaExit, roomId: cur})
				cur = info.prevRoom
			}

			pathLen := len(path)

			if pathLen > 0 {
				// reverse
				for i := 0; i < pathLen/2; i++ {
					j := len(path) - 1 - i
					path[i], path[j] = path[j], path[i]
				}