jaymakesgames

jaymakesgames | notes

Back

Auto-explore

In yesterday's note I touched briefly upon the auto-explore feature. Here is a little more detail.

On any given map, you might find things like enemies, farming produce, items, doors, etc. Navigating certain types of maps could be considered tedious; auto-exploration aims to remove that tedium.

The logic to drive this is as simple as possible:

- If the player is auto exploring
  - Any key pressed: stop exploration
  - Any visible enemies: stop exploration 
  - Any path we are already following:
    - Yes: move the player one tile along the path
    - No: make a list of all things that can be picked up (items, farming materials) 
          or interacted with (doors, chests)
      - Is the number of items in the list we just made > 0?
          - Yes: generate a path (A*) to each, choose the shortest, 
                 store it to follow in the next iteration
          - No: stop exploration

That's generally all there is to it.

You might be wondering why I didn't choose a simpler algorithm; something like:

- Same caveats as above regarding stopping
- Find the nearest-distance thing you can pick up
  - Move one step closer to it

This approach will work, however, it doesn't account for things like walls and other "blocks sight and/or movement" obstacles in the way. Here's an example to illustrate:

In the above scenario, both algorithms work well. The nearest object also shares the shortest path. What happens when we stick a wall in the way?

Here, the red item is nearest in terms of absolute distance, however the green item is on the shortest distance path. If we follow the "simple" algorithm, the player will pick up the items in red, green, yellow order. Seeing it live, the player will experience the character walking past an item (green) on the way to another (red), then backtracking to pick up the skipped item.

With the more complex algorithm, the pickup order wlil be green, yellow, red. This pickup order feels more like what the player would do if they were manually traversing the map.

Unsurprisingly, though, in practice I use a mix of both of these. Remember that the player can drop items wherever they please, or generate a huge farm that might place an item on every tile on the map. My A* implementation is not performant enough to query multiple hundreds of items. In cases where there are a lot of items on the map, I'll use the nearest-distance algorithm: it's very fast but not entirely "accurate". When there are only a handful, use shortest-path which is fast enough and more "accurate".

In the end, I suspect many players won't actually notice a difference. Auto exploration moves almost too quickly to follow what's happening in realtime. For me, it's nice to incorporate touches like this, though.