Sunday 31 August 2014

Guests, paths, and park borders

Until yesterday, guests were randomly walking around over the paths, buying things when they happened to pass a shop that sold something they needed.
They also didn't care about park borders, walking in and out of the park wherever the path went. Luckily they didn't have to pay an entrance fee!

I added an "activity" to a guest, a short term goal of what they aim to do. The first activity of a guest is now "enter the park". As soon as it reaches land owned by the park, the activity changes to "wander around in the park". Eventually, other activities will be added, such as "go to a ride", or "go home".

Making a guest stay in the park was then quite easy. Whenever a guest is "wandering", block any path leading to a tile that is outside the park. Since a guest starts wandering when it is inside the park, blocking the paths to non-owned tiles makes it stay in the park.

Having an activity such as "enter the park" is nice, but how does a guest find out where to go? For us it is easy usually, we see the paths, and can often immediately point out the shortest route to the destination. A computer can list all path tiles very quickly, you can teach it when two path tiles are adjacent, but it does not know easily which tiles to use for quickly getting in the park.

Luckily, three smart people figured out a solution to this problem a long time ago, and created an algorithm for it, which is known as A*. Basically, you try every possible direction that you can go at the same time (making copies of yourself to walk in different directions is easy in a computer). With every step (or tile) that you walk, you measure the distance that you walked, and you estimate the length of the remaining path. Since paths in FreeRCT are either in X direction or in Y direction (ignoring height for simplicity), the manhattan distance to the destination point is used as estimate. You add both numbers, and the position with the lowest sum is the best to try taking the next step. The rationale behind it is that if you walk in the "wrong" direction, the length of the walk increases, but the estimate also increases. The sum of both numbers thus gets bigger rather quickly. If you walk in the "right" direction, the length of the walk increases, but the estimate decreases (since you get closer to your goal), so the sum of both numbers stays more or less the same.

Positions in walks in the "right" direction get a lower sum, and are more favourable to explore further. Taking such steps continue until you found a position at the destination (or until you tried all paths that you can reach). When you reached the destination, the path is also known, and the guest at the junction knows whether to go left or right to enter the park.

You see both things in action in the picture. The two guests outside the park are trying to get to the park as quickly as possible, and walk straight rather than turn left to enter the park more to the north.
Guests inside the park 'bump' into the park ownership boundary, and wander back and forth on the three tiles that they can reach.

3 comments:

  1. Great explanation and examples of path finding! As a software dev, I'm excited to watch this project progress.

    ReplyDelete
  2. Replies
    1. No news, or rather, nothing is finished enough to show.

      Have been working on queuing, which needs rides that do not accept guests always (done), and guests that know how to queue (not done, as it interfered with work done by others).

      I switched to litter/benches/lampposts, adding graphics was simple and quick, extending the path gui messy enough to not even try, and simplify the stuff first in a dramatic way. Just started, the idea seems to work for the terraform window, now have to change the other windows with mouse interaction as well.
      Since it affects large amounts of code, it should be done carefully.

      Last but not least, since this year, real life started to interfere big time, which is not really helpful either.

      So, no news, but we're still here, no worries :)

      Delete