Follower logic in a maze environment?

[rtm223]

Yeah it is slightly simpler to do subtraction on closeness actually. Though I suggest you may wish to check out the adders in my blog, they will save you a tonne of effort and be more accurate, compared with the systems you describe above. You'll see why I say slightly

[tetsujin]

Yeah it is slightly simpler to do subtraction on closeness actually. Though I suggest you may wish to check out the adders in my blog, they will save you a tonne of effort and be more accurate, compared with the systems you describe above. You'll see why I say slightly

Dang, why don't I think of these things? Gotta say, though, it's been one of the exciting things about LBP2 - I look at what I've got to work with and feel like some critical piece is missing - and then it turns out somebody already figured out how to solve the problem...

I'm loving the whole logic thing in general - it was amazing how people could come up with complicated bits of mechanical logic in the first game, but it's also exciting to be freed of the timing and space and thermo constraints that all that mechanical logic would impose...

[Agarwel]

Argawel's idea is particularly prone (I think), to getting the ghosts stuck in corners or tight cycles.

I probably did not explained it in every deatail. But I must protest. That Idea would not stuck them at all.
When it would get to the juction it will always choose new direction. In this way:
If there are only two ways out then use the other than bacwards (two way are from turn. And we only want ghost to turn to the free way. Not to turn bacwars)

If there are 3 or 4 tags than:
1 - check if the pacman is up/down/left/righ and if the same way is free (by the tags on the juction). If yes - use that way. (we might also exclude turning backwards!) This would be pain for lots of AND logic. But shoul be matter of patience to cover to possible situations. Or maybe teher is some way to actualy optimalize it.
2 - if previous condition is not valid for any of the four directions - then use randomizer to choose ome of the free paths.

This way - the ghost wil lalways choose some way. If way leading to the side where pacman is is free - it will choose that one. Otherise some random.

[tetsujin]

I probably did not explained it in every deatail. But I must protest. That Idea would not stuck them at all.
When it would get to the junction it will always choose new direction. In this way:
If there are only two ways out then use the other than backwards (two way are from turn. And we only want ghost to turn to the free way. Not to turn backwards)

It could work. Pac-Man mazes aren't really hard to navigate after all... Limiting how frequently a ghost will reverse direction could be enough to save the ghosts from getting stuck.

More interesting info on the behaviors of the ghosts from the original game: (taken from here...)
[spoiler]
Blinky: The most cunning and most dangerous: Fast and trying to corner you with direction changes. When he's after you run quick and run twisty through lots of corners to shake (as with all others, cornering successive turn is most likely to lose the ghost). It also seems that Blinky does get a burst of speed when only a few dots are left in the maze. It is at it's most dangerous then. It will also track you by your poistion in the maze, trying to get to where you are as quickly as possible. It will try to line up with you vertically first, then horizontally. Blinky owns and patrols the top right hand corner of the maze.

Pinky: Fast but more predictable. Once he's on your tail he won't let go. But he'll stay on your your tail running after you, hardly trying any tricks. Pinkey will line up with you by always following the direction which you are moving in or facing. If Pac-Man and Pinky are heading toward each other, and there is a hallway just before he hits you, Pinky will turn into the hallway first and try to run in the same direction as Pac-Man. All this is explained by the fact that Pinky is hard coded into the program to read the movement of your joystick and follow it. Pinky owns and patrols the top left of the maze.

Clyde: Slower and a lot less harmful. Usually if you can stay out of the way of the top two (Blinkey and Pinkey) you can get away from Clyde and Inky by running through the maze. Clyde doesn't seem to want to line up with you or actively chase you. He just wants to get into your general vicinity and then only eats you if you happen to run into him. Clyde owns and patrols the bottom left of the maze.

Inky: The slowest and almost shy. Often when faced head to head he will turn and run away from you. Mostly he will only catch you if you happen to run into his pattern. Nevertheless it seems like it can adopt the characteristics of any of the others at any given time. All of a sudden shy Inky might try and outwit you like Blinky and you won't even know what hit you. Inky owns and patrols the bottom right of the maze.
[/spoiler]

Based on that it sounds like the original ghosts used rules similar to what you describe - not really navigating the maze but trying to reach Pac Man in various ways (lining up vertically or horizontally, forging a path through the maze, watching what direction the player's going, etc...) - lots of heuristics rather than a strict navigation solution.

[Agarwel]

Well it dpends if you really want it to be exact as the original.
In my opinion the pacman is not the kind of a game, where you need exact complex pathfindig (But if you have any ideal I would love to hear them to use if I iwll ever create sequel to my RTS - http://lbp.me/v/xhg8ft - It might really be handy there.)
But for pacman - I guess completelly random behaviour should be enough for 99.9% players (nobody will appreciate if you make same AI as he original. Nobody will probably even notice). And if you add just a basic logic - try to use the path leading to the pacman (even if not nearest path), than I guess it would really be enough.

Full pathfinding in the complex maze is nice. But probably for other kind of games. I dont want to hurt anyboy - but in Pacman I consider it waste of time.

[tetsujin]

Well it dpends if you really want it to be exact as the original.
But for pacman - I guess completelly random behaviour should be enough for 99.9% players (nobody will appreciate if you make same AI as he original. Nobody will probably even notice).

Well, the reason I cite the original behaviors is because the game's developers put some thought into the design of those monsters, and they work. That is, the result of those behaviors was an enjoyable game. People may not notice if the ghosts' behavior doesn't match the original - but they will notice if the ghosts' behavior fails to provide an enjoyable game play experience.

Completely random behavior - that is, not ever weighted toward any particular goal, would just result in the ghosts wandering around... I think you're right that a relatively simple set of rules is adequate for getting the ghosts around the maze in a satisfactory way - (and that's basically how it was done originally) but that's not "completely random"...

[mutant_red_peas]

Ungreth, have you tried to produce some of the ideas we have come up with yet?

I wanna play the Pac-man level!

[tdarb]

I know this thread is a week old, but I just got around to reading it. I have a different sort of thought on this. You guys seem to be focusing on the shortest path to pac man, which was my thought at first too, but then I thought "why do the ghosts need tags, they already have pathways?"

Since we know that walls will always be a set distance apart, and will always be either vertical or horizontal, I think there may be another option.

What if we made a flat square out of holo that is slightly larger than the pathways. Then, using the small grid, we cut the center portion out of each side of the holo square, so we have a gap on the north, south, east, and west edges. Inside of these gaps paste a new piece of holo with an impact sensor that can feel if it is touching a wall.

Now we have a holo square that we can place in, and it is aware of which pathways are open. We put a chip on there, and we add movers that allow us to select a direction of travel.

Now for the interesting bit. On each corner of the square we have made, we place tag sensors set to track the tag on pac man. using the analogue values for closeness we can determine which of the sensors is closest to pac man. This is the optimum direction, but we can't go diagonally. So we also find the second closest sensor, and this tells us which side is closest to pac man. Now we can move that way.

What happens if that direction is unavailable to us because of a wall? Well, then we use the third closest sensor in conjunction with the strongest to choose the second best path. If that is unavailable (eg a corner), we choose the third best path by using the direction between the second and fourth closest tags. In the case of a Third best path chosen scenario, the ghost would almost have to follow that path until it meets with a junction that opens up path option two, so it can avoid being stuck in corners.

I know I haven't worked out the whole thing in detail, but the logic seems sound to me. So, would this potentially work?