3
\$\begingroup\$

The game is an isometric RPG. The map is tile based.

I'm creating a town for this game. And I want one of the characters to roam the town randomly, because she is on a walk with her children.

I tagged the tiles she can go on. And I created a simplistic algorithm that I, in my naiveness, thought would be enough. Here it is:

If the character is blocked out and can't move in any direction she waits 1s before checking this again. If she can move in only one of the 4 directions, she moves that direction. If there is more than one possibility: If she can go forward, she always has 50% chance of going forward; if she can go both to her left and to her right there is an equal chance she chooses either of those two directions; and finally, if she can turn back, that chance is 2x smaller than turning to her left and 2x smaller than turning to her right. So, if she can choose from all 4 directions, she will have 50% chance to go forward, 20% chance to go to her left, 20% chance to go to her right, and 10% chance to go back. Repeat the above every step.

This algorithm fails beautifully. The character mostly moves randomly in one place. If she gets on a square she almost can't leave it.

I thought the solution would be to increase the chance of her moving forward. So I made the chance to go forward 5 times bigger than doing anything else. But this proved to hardly improve things.

COuld you give me some hints, point me to the correct direction? Or at least tell me that this is not worth it and I should instead resort to giving her a predefined path? (Are there no algorithms to make a character roam a given set of walkable tiles?)

Improve this question
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Can't you just make a graph of connected tiles, select a random tile and make her go there via an A* path planing/finding? \$\endgroup\$
    – Vaillancourt ♦
    Sep 26, 2017 at 18:02
  • \$\begingroup\$ This sounds like a fine approach. Perhaps it's the implementation that's failing? Have it run for a bit, sum up each choice, combine all the sums to see what percentages you're actually getting. Otherwise, I'd say you're changing directions too often. You'd more likely want to pick a direction and go forward for X tiles, then choose to continue, turn or go back with your percentages. \$\endgroup\$
    – House
    Sep 26, 2017 at 18:02
  • 1
    \$\begingroup\$ @MichaelHouse My current guess is that the complicated, full of obstacles structure of a town is the culprit. If she's on a square then only few tiles in comparision to the area of the square can give her any hopes of leaving the square (since the square's edge is much longer than the width of a street attached to this square). And if she gets to the park then the trees force her to change directions often, and as a result she basically runs around in circles. \$\endgroup\$
    – gaazkam
    Sep 26, 2017 at 18:13
  • \$\begingroup\$ @MichaelHouse And if she's on a street then let's hope the chances of her keeping the direction are large enough for her to walk to the end of the street, or else she'll be going this street back and forth. And what if we make her change the directions not so often? Then she'll always walk to the end of the street and never change her direction on junctions. \$\endgroup\$
    – gaazkam
    Sep 26, 2017 at 18:16
  • 1
    \$\begingroup\$ @gaazkam Then take Alexandre's suggestion. Provide her destinations that she navigates to. Go to the park, then the square, then B street, down to 6th Ave and back to the park. Choose the locations randomly, have her kids lead sometimes (as they will). It'll be far more natural looking than the random walk algorithm you have now. \$\endgroup\$
    – House
    Sep 26, 2017 at 18:21

1 Answer 1

Reset to default
6
\$\begingroup\$

People walking through a town usually have a destination. So when you want your NPCs wander behavior to look natural, they should also have one. It doesn't need to be a logical destination. Any destination will do to give a cursory observer the impression that this is a mentally sane pedestrian. (You could of course go the extra mile and give your NPCs a plausible daily routine or even a goal-oriented action planning AI, but it seems to me like this is currently far beyond your scope)

So just pick a random destination and calculate the shortest path to it. Then have the NPC follow that path. When the path is blocked, recalculate the path. When the NPC reached the destination, or the destination is unreachable, pick a new random destination and repeat.

In order to do that, you will have to implement a path finding algorithm. One algorithm which is very simple to implement and "good enough" when you don't calculate too many routes per second is Dijkstra's Algorithm. A more efficient algorithm which is slightly more complex (but still quite easy) is A*. There are many more route finding algorithms, but these are the two most famous ones which should belong to the standard repertoire of every game programmer.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ That'll teach me to write answers :P \$\endgroup\$
    – Vaillancourt ♦
    Sep 27, 2017 at 10:09
  • \$\begingroup\$ @AlexandreVaillancourt I didn't actually read the comments before writing my answer. \$\endgroup\$
    – Philipp
    Sep 27, 2017 at 10:42
  • \$\begingroup\$ Hehe ok, but you could have read the other answers :) \$\endgroup\$
    – Vaillancourt ♦
    Sep 27, 2017 at 10:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .