Moving bad guys in a maze

[kevin6569]

Are there some examples of Mobs moving around a maze?  I can control my main character with the controller, but can not figure out how to move bad guys independently and within boundaries. 

[kevin6569]

I'm using Intybasic for programming. 

[+cmadruga]

You may want to look up the book "Advanced Game Programming for Intellivision".

Check out the Oh Mummy game code.

[+nanochess]

I think IntyBASIC comes with the example game IntyPac that moves pseudo-ghosts in a maze.

 

Basically when the enemy is aligned on the 8x8 grid you read the cards in the four directions (up/down/right/left) and choose the one getting you near the player.

 

[gar0u]

For AI, you might want to check out the A* algorithm.  No idea if you can/need that horsepower.

[+cmadruga]

One thing to consider is how often the final destination will get updated, and the processing cost to figure out a complete path.

Sometimes it is better to just find a "directionally reasonable" next step, than to figure out the whole path to wherever you want to get to.

 

Also, @DZ-Jay mentioned the concept of "Manhattan Distance" during a recent presentation.

Something to consider when developing an approach.

[+DZ-Jay]

53 minutes ago, cmadruga said:

One thing to consider is how often the final destination will get updated, and the processing cost to figure out a complete path.

Sometimes it is better to just find a "directionally reasonable" next step, than to figure out the whole path to wherever you want to get to.

 

Also, @DZ-Jay mentioned the concept of "Manhattan Distance" during a recent presentation.

Something to consider when developing an approach.

The “Manhattan Distance” is a technique to compute what you called a “directionally reasonable” path.  That is, it computes cheaply (and naively) the distance from the starting point to the target through the various possible directions available, and picks the shortest one.

 

In this sort of algorithm (as suggested by @cmadruga) the idea is that you do not need a perfect solution, just a reasonable one that can get you to the goal.

 

How you compute the reasonable solution is separate question.  Manhattan Distance is one way; Direct Distance (as the crow flies) is another.  There are many others.

 

Any failures are compensated by recalculating it periodically and correcting with a new decision.

 

This is the kind of techniques employed in maze games like Pac-Man and Christmas Carol.

 

   dZ.

Edited July 15, 2021 by DZ-Jay

[+DZ-Jay]

Hi, @kevin6569,

 

Did the example mentioned above (IntyPak) help clear up the topic?

 

For reference, to move bad guys in a maze -- or in any play-field generally --you need the following:

• A way to determine the current location and direction of travel of the bad guy.
• A way to identify the target location or object to which you want the bad guy to move.
• A way to discern the paths available to the bad guy on his current location, or a means to detect walls and obstacles in his way.
• A way to determine which of possibly many available paths or directions is the most appropriate to take.

There are numerous ways that you can achieve each one of the above, but which one is most appropriate depends on the type of game, the construction of the play-field, the available information on the state of your player and enemy objects (e.g., directions, velocities, positions, etc.), and of course, the type or level of Artificial Intelligence you wish to apply to your enemies.

 

That last one is very critical, because the more accuracy and realism you demand, the more complex your techniques will be.  For instance, if you want your enemies to have full autonomy and omniscient means of targeting the player in a very accurate way, then you will need lots of state information, and a very intricate and perhaps complex path-finding algorithm.  Alternatively, if you think accuracy is not so important and a dumb A.I. is good enough, you may get away with something simpler like just pointing the enemies in the direction of the player, and hope for the best.

 

In Pac-Man (the archetypal maze game), these problems are solved in a rather simple and elegant way; but other games do it differently and still achieve success.  Again, it all depends on the demands of the game-play.

 

Christmas Carol and IntyPak, both being inspired by (or clones of) Pac-Man, they employ most of the same techniques, albeit implemented slightly differently.

 

So if your game follows the same style, you can use similar methods to those employed by IntyPak, which is readily available with source for you to study.  Let's take a look at how IntyPak addresses the points above.

 

• A way to determine the current location and direction of travel of the bad guy:
  The location of the enemy is easy:  the MOB has position coordinates; you just need to convert them into "grid" or "maze" coordinates.  IntyPac treats the maze as a grid defined by the 8x8 cards on the background.  That means that enemies (and the player) can only change direction when they enter a new 8x8 card with an open corridor.  So, you just need to convert the MOB position coordinates into their corresponding background card coordinates, and you get your position on the maze.
  
  The direction of travel is even easier:  IntyPak keeps a variable (dir) with a value corresponding to the cardinal direction in which the object is moving.  Every time the direction is changed (which will happen only on an 8x8 card boundary, as already mentioned), this variable is updated.
   
• A way to identify the target location or object to which you want the bad guy to move.
  This is where it gets interesting, and it has always been my contention that this is the "secret sauce" that makes Pac-Man (and Christmas Carol) special.  However, irrespective of how you pick which target to use, the method is always the same:  You need the grid coordinates of the target in order to compare them to the grid coordinates of your enemy.
  
  If the target of the enemy is a MOB (e.g., another enemy, some other object, or the player himself), then you do the same thing as we did before:  convert the MOB position coordinates to grid coordinates.
  
  If the target of the enemy is in the background itself (e.g., like a Power Pellet in a corner, or a specific spot on the maze, etc.), then you need to get the grid coordinates of their corresponding background card.
  
  IntyPak itself does not define targets for its enemies, opting instead to have them switch directions as they move, so as to make them more like unpredictable hazards rather than menacing hunters.  Still, it is useful to know that having a specific target in mind when determining which way to go, can enhance your enemy A.I., as will become evident in the descriptions below.
   
• A way to discern the paths available to the bad guy on his current location, or a means to detect walls and obstacles in his way.
  So, you have the grid coordinates of the enemy position and his direction of travel, now you need to know which ways he can go.  IntyPak does this by detecting the walls around the object.  Actually, it looks for the absence of walls to detect open paths.
  
  The idea is quite simple.  From the 8x8 card that the enemy object is on (its grid coordinate), the program checks in turn all the 8x8 cards around the enemy, up, right, down, and left, to see which ones are open.
  
  This is where the configuration of the play-field comes in:  In IntyPak, the maze is drawn using various cards depicting walls and items.  Each card has either a piece of wall, a single power pellet or, in the case of an empty corridor, nothing at all.  So detecting an open pathway is as simple as testing the card in the BACKTAB and seeing if it is empty (empty corridor) or has a pellet (still open path).
   
• A way to determine which of possibly many available paths or directions is the most appropriate to take.
  At this point you have the enemy's position in the grid, his target's position in the grid, and the possible directions in which he could move to get there.  Now it's time to find out which way to go.
  
  Pac-Man and IntyPak do this differently.  I will describe both so that you can see how such decisions impact game-play.
  
  The Pac-Man Way:
  Once you have the set of open path directions surrounding the enemy object, as described in the previous step, Pac-Man checks one at a time to see which one is closer to the target.  For instance, if the possible open directions are left and right, then the path-finding algorithm computes the distance between the card on the left of the enemy to its target, and the distance between the card to the right of the enemy to its target.  Then it chooses whichever direction results in the shortest distance.
  
  Here is an illustration from my presentation describing how Pac-Man (and Christmas Carol, which is based on it) work.  The red square represents an enemy ghost (Blinky), and the yellow square represents the player's object (Pac-Man).  The black arrows in each square are the current direction of movement of each object.  In this example, going right is computed to take 10 cards, while going left would take 12 instead, using the simpler Manhanttan Distance computation mentioned by @carlsson before.
  
  
  
  Notice that the Pac-Man algorithm does not really care about line-of-sight, or achieving perfect realism in this computation -- it bases its logic on a simple assumption:  the corridor in the direction closest to the target is more likely to be the one that gets the enemy closer to it.  This may or may not be true, but it does not matter, because on the next 8x8 card boundary we're going to do it all over again, and correct it as necessary.
  
  Thus, this simple algorithm gives the impression that the enemy is tracking or following the target and getting closer to it -- even though it may occasionally cause it to take what looks like the wrong turn.
  
  The IntyPak Way:
  IntyPak's path-finding method is even simpler.  As we alluded to before, it dispenses with enemy targets and just switches the direction of travel in an interesting way:  Once it gets the available open directions, it changes the axis of movement depending on the open paths.  In other words, if the enemy is moving horizontally, it picks an available direction in the vertical axis, and vice versa.  If no open direction is available in the new axis, it means that the enemy is in a straight corridor without junctions, and it continues moving in the direction of travel.
  
  As you can see, this is a much more simple way of finding a path, and when you play the IntyPak game you realize that it results in a much simpler game-play.  This is to be expected, for it was intended as an example of how to implement the concepts of a maze game, not as an accurate representation of a fully formed, production-quality game.  More advanced "A.I." is left as an exercise to the reader.
  
  Still, as the game illustrates, even such simple algorithms result in something quite playable and challenging.
   

I hope the above provides some useful guidance to you and others.  It should help demystify the concepts and techniques.  What's left is the actual code that implements them, and for that, there are plenty others here that can help.  Just ask.

 

For more information on the above concepts, check out the links below:

• The Pac-Man dossier
• From Pac-Man To Christmas Carol: A Game Post-Mortem
• Pac-Man To Christmas Carol Q&A

 

      -dZ.

Edited July 17, 2021 by DZ-Jay