From Pac-Man To Christmas Carol: Q & A

[+DZ-Jay]

Hello, everyone,

 

I thought I'd open up a Q & A thread on the topic I presented in the Virtual Expo 2020.  I noticed there were a few questions and comments I missed in the chat window -- what with being overwhelmed by the entire production, and being nervous to speak in public.  I will try to address those below as best as I can.  Feel free to ask anything else! :)

 

Considering that I went from zero game-development experience, to actually making a successful and beloved game, by the mere grace of many veterans who helped me; it is my genuine pleasure to be able to pay forward any wisdom I may have gained. :)

 

    -dZ.

[+DZ-Jay]

04:00:31    Carlos Madruga:    Manhattan Distance... interesting...

 

Yes, very interesting.  I honestly do not know how Pac-Man implements distance computation, for I've never actually looked through the source code, but it seems logical to assume that it also uses Manhattan Distance.

 

In any case, it is the solution offered by Joe Z. when I was struggling to optimize path distance calculations.  Euclidian geometry is quite expensive to compute on an Intellivision because the CPU lacks dedicated circuitry for multiplication and division.  This would be especially detrimental in a game like this because of the constant computation of multiple available paths by various enemies.

 

Manhattan Distance (also known as Taxicab Geometry), on the other hand, is quite easy to implement using only addition and subtraction:  Given two points on a two-dimensional grid, the result is the sum of the difference in each axis:

P1: (x1, y1)
P2: (x2, y2)

Manhattan Distance = |x2 - x1| + |y2 - y1|

 

Essentially, it's how many blocks you have to walk in each direction on a grid-plan, in order to get from one corner of the city to the other.  Hence the name.

 

For Christmas Carol, this turned out to be a great and easy solution to what I thought was a complex problem.  Live and learn, and thanks to Joe Z. for the suggestion!

 

   -dZ.

 

[timdu]

Can you tell us any details about a second release of Christmas Carol on cartridge?    In 2021 perhaps? Or is this top secret information at this time?

[+DZ-Jay]

39 minutes ago, timdu said:

Can you tell us any details about a second release of Christmas Carol on cartridge?    In 2021 perhaps? Or is this top secret information at this time?

 

Hi, @timdu, that's a great question.  "Christmas Carol Adventure" (aka "Christmas Carol 1.5," aka "Super Pro Christmas Carol," aka "Christmas Carol Supreme -- with extra sour cream") is planned for a Christmas 2021 release.  At least, that's the plan, such as it is.

 

As it should be apparent by now, these plans should be taken with a rather large helping of salt.  I may seem like a mild-manner programmer during the weekdays, but on my free time, I exercise my most impressive super-power:  procrastination.  More than a pro, I can castinate like a master! ?

 

[+DZ-Jay]

04:04:45    SteveJonesonlywatching:    so you can be in an open space but not be able to move in what looks like open space because you are not on the virtual tile path?

 

To be clear, the virtual map is implemented in such a way that it guarantees a sprite will never be in a tile from which it cannot escape.  That is, adjacent tiles share their exits.  So being able to move, say, to the right on one tile, implies that you can move to the left from its neighbor to the right.  This is the basic principle, in Pac-Man as in Carol.

 

The main mechanical difference in the virtual map between Pac-Man and Carol is in the resolution:  Pac-Man tiles coincide with the background cards, so every card used to draw the maze (a straight, a corner, a junction, a wall, etc.) is potentially part of the map.

 

Carol tiles, on the other hand, are half the resolution of the background cards.  To account for this (and to be able to implement Pac-Man faithfully as originally intended), the virtual map is slightly offset from the background cards.  Take a look below and notice that the "path" connects the center of the background tiles and that the virtual tiles at the edges of a background tile are not part of it.  Those appear as black squares in the image below.

 

 

This gives an identical result to the way Pac-Man works:  the sprites can only move across the center line of the path and turn only at the center point of a tile.  It's just that Pac-Man tiles are the same size as the visual background cards.

 

The sprites in Christmas Carol can only move through those tiles aligned with the center of background cards (just like Pac-Man), leaving a lot of empty space.  This is why Carol and her enemies "zig zag" their way around the open play-field:

 

 

So then ... if the path is still constrained to the center of the background cards, why is the virtual map in Carol smaller?  The answer is quite simple:  to give a higher resolution to the enemies in making their path calculations.  Remember, if the play-field is twice as big in Pac-Man than in Carol, and Pac-Man's enemies make decisions every 8 pixels (the distance between two tiles), then making Carol's enemies make decisions at the same rate would result in a much slower reaction time.

 

This, in my opinion, is one of my key innovations in what was intended to be the "definitive" port of Pac-Man to the Intellivision:  We scale the play-field, but we also scale the sprites' speed, and consequently their animation and decision rates.  All in order to maintain the balance of the original.

 

Let me know if this does not answer the question.

 

    -dZ.

Edited November 22, 2020 by DZ-Jay

[+DZ-Jay]

04:05:48    Carlos Madruga:    How often do enemies recalculate the path based on the most recent player position?

 

Very good question!  The enemies' "pathfinder" routine is called as soon as they enter into a new virtual tile.  As shown in the presentation, at that point they choose the shortest path to their target tile and commit to that direction, but they will continue moving in the current direction until they reach that tile.  When they reach the new tile, they "turn" by switching to the last committed direction, and call the pathfinder routine again.

 

Moreover, you may remember from the presentation that the turn actually takes a few steps to complete:

 

 

As soon as the enemy enters a new virtual tile, the actual process has the enemy "look" in the new direction, but continue to move in the previous one, until it gets aligned with the path at the center of the tile; at which point it actually can start moving in the new direction:

 

 

If you look carefully in Christmas Carol (as in Pac-Man), you will see the enemies changing their orientation early, giving you an indication of which direction they will travel next.  It's more subtle in Christmas Carol since the distance to travel is merely 4 pixels between tiles, but the effect is there and quite noticeable.

 

Once again, this is the underlying mechanism of Pac-Man as well as Carol.  It's the generic "combustion engine" that makes the proverbial car move.  What makes a car special and different from another is all the stuff built on top and around it.

 

By the way, you will noticed that I said "shortest path to their target tile" rather than "to the player position."  This is important, for in Carol as in Pac-Man, the sprites do not necessarily base their targets on the player position directly, and sometimes at all.  Which target an enemy follows and how it chooses it, is the actual secret sauce that makes Pac-Man such an enduring and enjoyable classic -- it's what gives each individual ghost its identity, and what imparts on it what appears to be rational behaviour and personality.

 

I'd like to think that the same is true for Christmas Carol's design choices on the matter. ?

 

    -dZ.

Edited November 22, 2020 by DZ-Jay

[+DZ-Jay]

04:15:22    SteveJonesonlywatching:    what would you say was your main contribution to the game versus what Joe contributed? ie what was the division of the creative input?

 

While I am forever indebted to Joe for his wonderful help, motivation, mentoring, and technical assistance throughout the development process; I don't think he would disagree if I  claim that Christmas Carol is my own creative and development work.

 

That's not to diminish his credit at all.  I will go further and say that during the original three-weeks project that turned Pac-Man into Christmas Carol back in December 2010, we both were constantly working on getting it running.  Joe offered technical solutions to some problems, sometimes even algorithms and code, but I would then have to adapt these into my framework or implement them wholesale.  He served as a sounding board to my ideas, and provided feedback and expertise.  And of course, he created those fantastic sound effects which give life to the entire game!

 

You actually can read all about that stage of the project in the tread titled "The Birth Of Christmas Carol."  It shines a stark light on our great collaboration, and gives a bit of insight into how the story and characters of Christmas Carol's world evolved.

 

Joe's participation in the 18-month journey that took that "prototype" into a full-fledged CIB production was more attenuated, mostly because the underlying framework was a bit more stable and I've already gained enough experience to take the training wheels off.  He still was one of the primary testers and contributors of ideas, plus he published the game in a phenomenal gatefold box with an awesome cartridge and sticker, and handled all the logistics for release.

 

If you want more information about Joe's and other's contributions, check out the credit sequence, which plays from the title screen of the game.  They are also at the end of the game's manual. :)

 

     -dZ.

[+DZ-Jay]

04:15:59    Anders Carlsson:    Did you know that Christmas Carol vs. the Ghost of Christmas Presents is by far the most played game in the AtariAge Classic Games Tracker? Currently at 13340 minutes (222 hours), with Tower of Doom in second place with a mere 4578 minutes.

04:18:10    Anders Carlsson:    Actually it is still the fifth most played game ever, covering every games system from 1972 to 1999.

 

Wow!  I did not know that!  I'm humbled.  ?

 

Then again, I bet you anything that a good chunk of those hours came from the few guys who beat the game over and over and rolled over the score to yellow.

 

    -dZ.

[+DZ-Jay]

04:22:33    Carlos Madruga:    Looks like a pretty powerful framework used for this game. I wonder if Intybasic coders might somehow benefit from it to make better games.

 

This has been discussed in the past.  Unfortunately, the P-Machinery framework is not a good fit for IntyBASIC's programming model, at least not right out of the box.  That is not to say that IntyBASIC is wrong or insufficient; they both offer two distinct ways of approaching the problem.

 

The main barrier to easy integration of the two is that in the IntyBASIC model, the "main" program runs for as long as it needs to, doing all the work needed to compute a frame in sequence, and then relies on the program synchronizing itself with the display interrupt routine via the "WAIT" command.

 

In contrast, P-Machinery treats the display interrupt routine as the "main" program, which then triggers appropriate events according to the results of computing the frame.  These events are queued up, then executed in sequence outside the critical path, each one queuing up its own events as necessary.

 

The display interrupt routine in P-Machinery is the game's engine, and it includes the event queue manager.  In order for this to work in IntyBASIC, you would have to re-arrange the way that IntyBASIC handles the display interrupt, which unfortunately, is not directly available from the language itself.  Consequently, you would have to replace the "epilogue" and "prologue" libraries with a custom one.

 

It's not impossible, and perhaps not even that hard, but at that point it's just a "BASIC" compiler on top of an entirely different programming framework, which may run counter to Oscar's designs.  It would render useless most of the higher-level features of the language, reducing it mostly to a fancy "if/else" expression compiler.

 

That said, it may be a project I could tackle -- if I ever finish the framework for release.

 

    -dZ.

 

Edited November 22, 2020 by DZ-Jay

[+DZ-Jay]

04:27:29    Carlos Madruga:    Small tester pool is indeed a problem with homebrew creation. Any ideas on how to compensate for that, other than just paying people to test your game?

 

This is an excellent question, one in which I hope others will chime with their own ideas.  A small pool of testers is indeed a problem in our community, mainly because it is such a small community to begin with.

 

In my view, the best way to increase the size of the pool is to reduce the friction for people to join and motivate them to participate.  For ideas on this, I usually try to put myself in other people's shoes:

 

Honestly, I have a life and a job, and I'm growing older increasingly faster each year, cutting my time shorter each time.  So why would I spend any of it, and apply any effort in something that provides value to someone else?  A few answers come to mind immediately:

• Because I know the person, and I wish them to succeed, and would like to help as I can.
• Because applying my effort is quite easy and painless, and perhaps even a bit of fun.
• Because I'm excited about this particular project and would love to get my hands on it early.
• Because the person promised to reward me with money/in-game credits/free game/merch or loot/etc., for my trouble.
• Because finding a pernicious bug in a game can be a big challenge, and big challenges are my thing.
• Because the person has a high standing reputation in my community, is someone I respect and admire, and I would feel honour to assist in some way.
• Etc.

Not all of them apply to everyone, and still there may be many other motivations which are unique to others; but from that we should be able to figure out how to make the prospect more appealing.

 

Let me be more blunt:  if your approach to potential testers is just a plain and cold, "here's my new game, does anybody want to give it a try?"; then you may want to reconsider your own motivations.

 

Get to know people; build up your own reputation by helping others; engage the community and participate in various projects; offer players something in return for their efforts -- even if it is just to mention their names in the screen or manual; make the endeavor seem fun and engaging and personal; not dreadful, boring work to make you look good.

 

Also, make sure to focus on making it easy and convenient for others to participate and provide feedback.  Not many things will reduce your pool of testers more than forcing them to jump through hoops and follow arcane rules and processes in order to provide what is essentially to your benefit.

 

That's what worked for me.  I made tons of friends in AA during the development of Christmas Carol, and I first got to know a lot of them during design and feedback conversations in the beta-testers mailing list I created for it.  Everyone was invited, even a bunch of people who joined for the sake of getting a free ROM and never offered any feedback.  It did not matter, plenty others did.

 

If it's easy and painless, quick and convenient, and your game is fun and interesting, and your approach is nice and sincere; then why wouldn't they jump at the chance to play?

 

Anyway, I would love to hear what others have to say.

 

     -dZ.

Edited November 22, 2020 by DZ-Jay

[+DZ-Jay]

Here's a follow up question transplanted from another thread:

  

1 hour ago, CrazyBoss said:

Thanks dZ. And thanks again for a great show Saturday. I would like to know abit more in detail about the ai for the ghost. I know you explained it before, but maybe could supply a bit of pseudocode.

 

First, as you may recall, the Ghost in Christmas Carol follows the same rules as all other enemies in Carol and Pac-Man.  That is, it moves in the virtual tile map, looks ahead as soon as it enters a new tile, computes the shortest available path to its target tile, and commits to its new direction.

 

That is important to keep in mind because the "AI" of the Ghost, as with any other enemy, is essentially the logic used to figure out what that target tile is.  Everything else is just the standard boilerplate machinery used by all enemies.

 

With that in mind, let's get to the point:  how does the Ghost figure out its target?  It's quite a simple thing, really.  The magic is in the way the individual rules employed, work in combination with the rest of the enemies and the player interactions, from which a more complex behaviour emerges.

 

First a bit of technical trivia:

• The Ghost has an internal counter that keeps track of how many tiles he travels as it moves.
• Actually, he is given a specific number of tiles to count at the start of each level, which is part of the difficulty parameters for each maze.
• The Ghost then counts down the tiles he traverses as he roams the play-field.
• When the counter reaches zero, he switches states briefly, re-calculates a new target, and resets the counter.
• The entire process is repeated throughout the life of the level.

So now, on to the description of the algorithm.

 

The Ghost starts each level with a full counter and engaged in his "Roam" mode.  The first thing he does is pick a random number from 1 to 8, corresponding to the locations of the presents on the maze.  It does not matter whether Carol has already picked up the present, the Ghost may choose its prior location as its target.

 

He then uses the normal pathfinder logic described before to move towards that target, counting down the tiles as he moves through them.  If he reaches the target before the counter runs out, he will immediately pick another random present location to target.  However, he does not reset his tile counter, increasing the likelihood that it will reach zero soon enough.

 

If the Ghost's tile counter reaches zero before he reaches his target, he enters "Look Around" mode:  he stops right on the tile he is on, and engages the Auto-Pilot with a randomly selected script from a pool of eight available "look around" sequences.  These vary from short "look left, then right" sequences, to more elaborate ones like "look left, then right, up, then down, then do a double-take; clench the eyes and shake."  With the Auto-Pilot engaged, the collision detection routine is disabled, so the Ghost is essentially harmless, just standing there, looking around like a dummy.

 

When the script concludes, it resets the Ghost back to "Roam" mode, which has him pick a random present for a target, and the cycle continues for the duration of the level.

 

As the level progresses and Carol picks up a present, the Ghost immediately switches targets to the exact location from which Carol picked it up.  He will not target Carol, only the place where she was in.  If the player is quick and savvy enough to notice this, he can avoid the Ghost altogether by moving in the opposite direction.  However, more often than not, the bewildered player ends up moving in what turns out to be the Ghost's path to his new target, and BAM!  Carol loses her presents.

 

The end effect of the logic above is that the Ghost appears to be running around from one end of the maze to the other, occasionally stops and forgets where he was going, and eventually continues roaming around.  He doesn't know who Carol is nor what she's doing, but he will be alerted to her presence whenever he senses that one of "his" presents was taken.

 

It makes him look a little goofy, and alarmingly unpredictable, and just an all-around nuisance who gets in your way from time to time.

 

As you can imagine, the balance of difficulty can be tuned by changing the number of tiles in the counter.  The higher the count, the longer the Ghost will travel before stopping and re-targeting.  Because the Ghost moves so much faster than Carol, this increases the chances of getting in her way -- especially when she picks up a present and the Ghost just bolts towards that same spot.  After all, Carol must move around and pick up those presents, and there's an Evil Snowman rampaging around as well!

 

Reducing the number of tiles in the counter has the opposite effect:  it decreases the likelihood of the Ghost ever reaching any of his targets, including the spot where Carol is when she picks up a present; giving her a much needed respite.  Moreover, because the Ghost becomes harmless to the touch when he stops to look around, Carol has more chances to escape him by building a greater distance between her and the Ghost.

 

This seemingly complex orchestration of what are essentially rather simple rules, is one of those emergent behaviours that so fascinated me when observing Pac-Man in my youth.  The Ghost Of Christmas Presents' AI in particular, is a key ingredient in that delicious recipe that is Christmas Carol, one that makes it stand distinctly apart from its Pac-Man heritage.

 

As I said during the presentation, and I continue to insist, the underlying machinery that Carol takes from Pac-Man is just the raw materials from which a game is forged.  Pac-Man has its own fabulous way to impart complex and interesting emergent behaviours on its enemies; Carol has her own.

 

     -dZ.

Edited November 22, 2020 by DZ-Jay

[+DZ-Jay]

04:34:40    David Akers:    I remember the first roms got lots of testing but after 30 some releases the later versions got less testing...

 

Not a question, but an observation, related to the point above about growing the pool of testers.  This is something I mentioned in my retrospective as well, because it is one of my primary lessons learned:  "Beta Fatigue."

 

Christmas Carol was on "beta" for an entire year.  Enthusiasm was great at the beginning and lots and lots of feedback.  10 months or so and 30-some "beta" releases later, only a couple of people were still giving it a go.

 

I blame myself for the long release cycle.  Everyone's help was invaluable throughout those 18 months of development, and some new features came as a result of brainstorming together with the group of beta testers.  Some even made it into the final game.  However, it was too long and too much.

 

The first production version of Christmas Carol, the one released at the CGE in 2012, is tagged as "2.34" -- that means that there were 34 revisions that were released to the beta testers from the start of project.  Who's got the stamina for that? ?

 

    -dZ.

[+DZ-Jay]

04:34:43    5-11under:    Tell a bit more about the direction heuristics, if you could.

 

It's quite simple and elegant, it's almost magic.   Below is a high-level description of the algorithm, skipping through the technical details of actual signal decoding and sampling.

 

First consider the following diagram, taken directly from the P-Machinery source code:

;;  NOTE:   The disc is divided into 4 distinct regions for each of the     ;;
;;          cardinal points. Each region corresponds to 3 discrete disc     ;;
;;          positions, which expressly exclude the diagonals. The resulting ;;
;;          disc layout is illustrated below:                               ;;
;;                                                                          ;;
;;                        F   0   1                                         ;;
;;                   E     N..N..N     2                                    ;;
;;                     x  ';:::::;'  x         Legend:                      ;;
;;                D        ';:::;'        3    -------------                ;;
;;                   W:,     ':'     ,:E       N: North    ^                ;;
;;                   ::::-_   v   _:::::       E: East     >                ;;
;;               C  W::::::"> + <"::::::E  4   S: South    v                ;;
;;                   :::::-'  ^  '-:::::       W: West     <                ;;
;;                   W:-"    ,:,    "-:E       x: Invalid                   ;;
;;                B        .;:::;.        5                                 ;;
;;                     x  ,:::::::,  x                                      ;;
;;                   A     S''S''S     6                                    ;;
;;                        9   8   7                                         ;;
;;                                                                          ;;
;;          If the translated disc input results in one of the invalid      ;;
;;          diagonal values, the disc event is processed in a special way.  ;;

 

As you can see, the four cardinal points are slightly expanded to include the immediately adjacent directions, to create the normal directional zones.  If your thumb lands on any of those four areas, it will be interpreted as a desire to go in the corresponding direction.  So far, this is the way many games already treat the hand-controller.

 

The problem is with the so-called perfect diagonals, which are ambiguous because they are equidistant from two of the cardinal points.  Many games do not account for these, creating "dead zones," which are either ignored (sub-optimal), or interpreted as no input, or idle (potentially bad for the player).

 

The "Joy Disc" decoder uses a special set of rules to disambiguate the perfect diagonals, making some assumptions about the player's intent.  Some of these assumptions are:

• We assume the player is rolling his thumb on the disc, as the inty-gods intended it to be, and not just "pressing buttons."
• We assume that the player is playing for, you know, fun; and not trying to "break the system" to find its flaws.
• We assume that the player is using the disc in good faith, trying to run around the play-field effectively, and not just randomly pressing control surfaces.

 

The algorithm:

1. Decode the disc input into one of the 16 directional values.
2. If the decoded value is one of the valid directional zones, we accept it.
3. If the decoded value is one of the perfect diagonals, process it further:
   1. Compare the new decoded value against the last valid accepted value.
   2. Accept the next cardinal point in the direction from the previous to the new one.
4. Return the accepted value.

What this means is that we assume that the player is rolling his thumb on the disc and that the signal sampling rate is faster than his movement.  So, if he was going, say, North, and we detect a North-East diagonal, we just assume that the player intended to go East, and was in fact rolling his thumb in that direction just when we caught it, right before he made it.  So, we commit to that new direction.

 

Ultimately, because the player's movements are constrained to the walking path of the virtual tile map, the whole system sorts itself out by discarding the input if indeed that direction is an invalid one.  In such situation, consider that there is no other possible input which we could accept:  if the player is moving North and pressing North-East, but there's a wall to the East; we just continue moving North ignoring the input, and avoid annoying the player.

 

In practice, this scheme opens the possibility of accepting the actual valid direction in which the player intended to go without much downside.

 

This is one-half of the reason why Christmas Carol appears so responsive.  The other half is ... that it is indeed so responsive.  I mean, the disc is sampled in real time, in between display interrupts.  This is in contrast to most games, which sample the hand-controller input at 60 Hz, right after moving sprites, checking collisions, and computing the current frame.  Thus, the new input is always processed on the next frame, delaying the player's reaction to the action on the screen.

 

This is fine for most games, but for frantic action, twitch-reflex games like Pac-Man and Carol, we could use something better.

 

P-Machinery samples the hand-controller in between frames, so by the time the next interrupt hits, we are guaranteed to have the latest direction the player has chosen, and can move sprites, check collisions, and compute the new frame with this information.

 

Oh, and to be sure, lest anyone imagines that this is some new development, this particular scheme has been in the code since the very early Pac-Man days of the project.  That and Pac-Man's fast-cornering were some of the key features I implemented for my "definitive" Pac-Man port, back in 2009.  But that's a story for some other day.

 

     -dZ.

Edited November 22, 2020 by DZ-Jay

[+DZ-Jay]

For anybody interested, below are links to the original release of the Christmas Carol game here in AA, from 2010, and the development thread of the eventual production release.

 

 

[+DZ-Jay]

During development, I worked out most of the path-finding and AI logic of the enemies by writing it in a C-like pseudo-code.  This allowed me to figure out the decisions and proper logic flow, then it was just a matter of "mentally compiling" the code into Assembly Language, and optimizing it from there.

 

Because a few people had asked for it, I include below some of these routines taken directly from my original "Christmas Carol" development documents.  Have a look and ask any questions.

• move_elf.c - Routine to move Carol within the virtual tile map.
• move_enemy.c - Routine to move an enemy within the virtual tile map.
• target_snowball.c - Targeting routine for the Snowball, to determine its target tile.
• zap_elf.c - Routine used by the Bad Toy to detect line-of-sight to Carol and zap her with his laser.

 

Feedback and questions are welcomed!

 

    -dZ.

 

[+DZ-Jay]

There is one critical point I kept forgetting to mention, in the presentation and in this thread.  It is a key assumption in the enemy's targeting logic in both Pac-Man and Carol:  The enemy is not allowed to move backwards.

 

I just took this point for granted as I talked about the path-finding logic, but it must be said expressly:  When the enemy looks ahead to the next tile in the current direction of travel, and finds the available exits from there; the exit that points to his current location is explicitly removed from the set to prevent it from going backwards.

 

So the simple algorithm to find the path looks like this:

• Identify the current virtual tiles of the enemy and its target.
• Look ahead to the next tile in the current direction of travel.
• Identify the available exits.
• Discard the exit which is opposite to the current direction in the axis of movement.
• Compute the Manhattan Distance to the target from the tile pointed to by each exit.
• Pick the shortest one.
• Commit to the new direction.

The other point that I wanted to clarify is regarding the path calculation:  To be sure, we are not computing the path through the virtual map; we are merely computing the Manhattan Distance between the enemy and its target, without regard to any walls or unavailable exits.  The point is not for the sprite to find its way, but for the sprite to make a decision on what direction to go when it reaches the next virtual tile.

 

This is a very dumb algorithm -- the enemy really doesn't know where he is going, he just makes incremental decisions at each tile.  In practice, it results in a very effective means to find his way, adjusting as he goes along, and giving him an opportunity to improve on his previous decisions.

 

I hope this makes it clear.

     -dZ.

[+cmadruga]

22 hours ago, DZ-Jay said:

04:00:31    Carlos Madruga:    Manhattan Distance... interesting...

 

For Christmas Carol, this turned out to be a great and easy solution to what I thought was a complex problem.  Live and learn, and thanks to Joe Z. for the suggestion!

Thanks for the Q&A thread, and for revisiting my comment.

For Infiltrator I used Euclidean distance without the square root. I may try the Manhattan Distance method to see if in my case there would be a noticeable performance benefit.

 

A related question, if you don't mind. How do you solve for 2 or more paths that have the same distance?

I saw a video of Carol a while ago, it showed an enemy getting stuck going back and forth. I don't know if what I mentioned could have been the cause.

Having played the game myself I never observed that issue, so either way I assume it was probably something already fixed.

 

 

 

[+DZ-Jay]

16 minutes ago, cmadruga said:

Thanks for the Q&A thread, and for revisiting my comment.

For Infiltrator I used Euclidean distance without the square root. I may try the Manhattan Distance method to see if in my case there would be a noticeable performance benefit.

 

Be aware that there is a very big caveat that comes from Manhattan Distance ...

16 minutes ago, cmadruga said:

A related question, if you don't mind. How do you solve for 2 or more paths that have the same distance?

 

Yup, that's the one:  because you are computing the straight paths across a grid, multiple paths may result in the same distance even though one may be actually shorter than the other as the crow flies (i.e., in Euclidean geometry).

 

Because in Pac-Man (as in Carol) the sprites move on a two-dimensional grid, this is fine:  They can't really travel like a crow, so being shorter in that manner does not really help.

 

The solution to ambiguity in Carol is even simpler than the rest:  we choose the first exit, counting clockwise, starting from North.  In practice, the selection is done like this:

1. Starting from North and going clockwise, compute the Manhattan distance.
2. Store this direction as the most likely candidate.
3. Move to the next direction and compute its Manhattan distance.
4. If it is lower than the stored one, replace it.
5. Continue until all exits are exhausted.

In the end we have the shortest one or the first one found of multiple paths with the same shortest distance.

 

I believe Pac-Man treats step #4 in reverse:  instead of keeping the previous one if they are equal, it picks the new one.  Thus, it gives preference in this order:  West, South, East, and North.  Carol prefers the other way around. :)

 

16 minutes ago, cmadruga said:

I saw a video of Carol a while ago, it showed an enemy getting stuck going back and forth. I don't know if what I mentioned could have been the cause.

Having played the game myself I never observed that issue, so either way I assume it was probably something already fixed.

 

That is actually true.  Because of the way the targeting works, the player can position Carol in such a way that forces the Snowman to go around in a rather tight loop.  The Snowman is always trying to get to Carol, so if he is behind a particular configuration of walls and Carol is in the opposite end, he will try constantly turn trying to find the shortest path, and finding always a wall in his way.

 

I thought of various ways to break this loop and force the Snowman to move out of it, all of them requiring invasive changes to the elegant targeting mechanism.

 

However, in the end I decided to leave it alone.  In practice, this only happens when Carol is standing idle in a particular corner.  The moment Carol moves out of that spot the Snowman will go after her and break out of his loop immediately.  Therefore, this will only happen when the player is essentially not playing the game, so why do we care?  In order for him to actually complete the level, he'll have to move Carol sooner or later, and the Snowman will follow suite.

 

If the player just stays there, let them get bored to death just staring at the Snowman go round and round. :)

 

Here's an old example from when Joe and I first found the issue:

 

I view it not really as a bug, but more like the Snowman is lurking, waiting for Carol to come out, so he can pounce on her.

 

Here's another example I mocked up to describe the problem.  There's actually a present where Carol is standing, so picking it up will cause the Ghost to immediately turn towards Carol, colliding with her.  This results in all the presents being reset, which will cause Carol to pick it up again, only to have the Ghost turn right around towards her and hit her again.  Over and over, this goes on until the player moves out of the way and lets the Ghost go somewhere else.

 

 

These are very old issues discovered with the targeting mechanism.  Like I said, in practice, they turn out not to be a big problem.  Once the player gets bored of watching the enemy loop, he'll just move Carol and continue. :)

 

     -dZ.

[+cmadruga]

Having played with pathfinding in a couple of my games already, and without really having any sort of in depth computer science background...

I feel like getting stuck is such a recurring problem, and I'm surprised not to find any mention to a standard "snap out of it" type of logic.

Maybe those things exist, and I just haven't found them. Or maybe I'm just not asking the right question. It sounds like you looked into that.

 

I'd think ideally the last few positions should be stored, and in case of a circular pattern, maybe the second-best path should be picked up for once.

Of course, that tends to introduce complexity and has an associated cost, but at the end of the day I was hoping to piggyback on solutions from people smarter than me.

 

Does that make sense?

Edited November 23, 2020 by cmadruga

[carlsson]

22 hours ago, DZ-Jay said:

I bet you anything that a good chunk of those hours came from the few guys who beat the game over and over and rolled over the score to yellow.

While my detailed stats are not 100%, it would seem that Darrin9999 is the individual who logged the highest amount into your game, about 61 hours, with Opry99er following at 40 hours and then another bunch at 17-23 hours each. I have detected that you logged almost 10 hours yourself, plus another few who played it in smaller quantities, about a dozen different people logged their times during the years.

 

I suppose with the Christmas season approaching, it might be time to increase those numbers. If anyone would want to join the fun - even if only for a week - you can post your times in the tracker. Of course this applies to every Intellivision game (and other formats), not only Christmas Carol.

[+DZ-Jay]

2 hours ago, cmadruga said:

Having played with pathfinding in a couple of my games already, and without really having any sort of in depth computer science background...

I feel like getting stuck is such a recurring problem, and I'm surprised not to find any mention to a standard "snap out of it" type of logic.

Maybe those things exist, and I just haven't found them. Or maybe I'm just not asking the right question. It sounds like you looked into that.

 

I imagine that the reason there isn't a standard mechanism is probably because of two main reasons:  First, like any other problem, there can be myriad ways of solving it.  Second, and perhaps more importantly, it may not be really a problem in practice, and solving it may be more costly than its worth.

 

That second bit is the reason why I did not attempt to solve it.  The path-finding algorithm is simple, and elegant, and works exceedingly well for 99.99% of the time.  When that 0.01% of the time it breaks down, what is the actual consequence?  That the enemy looks stupid while the player remains motionless.

 

Now, is it really worth going through the trouble of implementing potentially costly solutions that may even have a negative impact on the other 99.99% of the time, for what is, in essence, a rare edge case?  In my humble opinion, on Christmas Carol at least, it was not.  You yourself said that you've played the game and never encountered it.  The same applies to most players.

 

In my view, I treat the player as a partner, not as an adversary.  My job as a game programmer is to enhance the enjoyment of the player, and to avoid annoying him.  In turn, I expect the player to interact with the game in good faith.  If this were something that breaks the normal use of the game, then yes, we have to fix it.  But if it is just a quirk that may look a little goofy and only triggers rarely, and will solve itself out if the player continues playing normally; then I have better things to do.

 

Quote

I'd think ideally the last few positions should be stored, and in case of a circular pattern, maybe the second-best path should be picked up for once.

Of course, that tends to introduce complexity and has an associated cost, but at the end of the day I was hoping to piggyback on solutions from people smarter than me.

 

Does that make sense?

Yes, it makes sense.  It is also similar to what I had thought about before.  As you note, it does require that we keep track of the previous positions and compare, which is something that is not built into the mechanism to begin with, and complicates it.  It also requires additional memory and CPU resources to process.

 

Of course, if it is something that negatively affects game play (which may be the case in your particular game), then that expense may be warranted.  If you have a specific case, I can work with you to come up with solutions, just let me know.  However, I wouldn't consider myself smarter than anybody.

 

     -dZ.

Edited November 23, 2020 by DZ-Jay

[Sinjinhawke]

It's Christmas Eve day and I'm waiting for my boss to say "take the rest of the day off Chris, it's Christmas Eve".  So far he hasn't and I think he signed off for the rest of the day.  Worst boss ever.

 

Decided to play some Christmas Carol for the first time since it's raining and I don't like running in the rain during winter.  

 

Fantastic game but now I feel stressed out.  That ghost.  That f#@%ing ghost.  I hates it.  I hates is forever.   

 

First game got under 300 points.  2nd game got 723 points and made it to level 10.

[IntyFanMatt]

38 minutes ago, Sinjinhawke said:

It's Christmas Eve day and I'm waiting for my boss to say "take the rest of the day off Chris, it's Christmas Eve".  So far he hasn't and I think he signed off for the rest of the day.  Worst boss ever.

 

Decided to play some Christmas Carol for the first time since it's raining and I don't like running in the rain during winter.  

 

Fantastic game but now I feel stressed out.  That ghost.  That f#@%ing ghost.  I hates it.  I hates is forever.   

 

First game got under 300 points.  2nd game got 723 points and made it to level 10.

We’re playing Xmas Carol in the High Score Club right now, so just take a pic of your best score and post it in that forum!! Would be cool for you to join us!!

Edited December 24, 2020 by IntyFanMatt

[+DZ-Jay]

1 hour ago, Sinjinhawke said:

It's Christmas Eve day and I'm waiting for my boss to say "take the rest of the day off Chris, it's Christmas Eve".  So far he hasn't and I think he signed off for the rest of the day.  Worst boss ever.

 

Decided to play some Christmas Carol for the first time since it's raining and I don't like running in the rain during winter.  

 

Fantastic game but now I feel stressed out.  That ghost.  That f#@%ing ghost.  I hates it.  I hates is forever.   

 

Nah, he's not too bad.  Just remember that he runs at you when you pick up a present, so if you are about to pick up one and he is close by, you may want to wait for him to go away, or aim for another present.

 

Also, as described in my comments above, he will stop every so often to look around.  At that point, he won't notice you picking up presents, so it's a good time to go for it.

 

1 hour ago, Sinjinhawke said:

First game got under 300 points.  2nd game got 723 points and made it to level 10.

Ah!  That's a great score, really!  Level 10 of 16, that's 5 stages of 8, you're almost there -- you can save Christmas! ?

 

[chargrdan]

On 11/22/2020 at 11:53 AM, DZ-Jay said:

 

Hi, @timdu, that's a great question.  "Christmas Carol Adventure" (aka "Christmas Carol 1.5," aka "Super Pro Christmas Carol," aka "Christmas Carol Supreme -- with extra sour cream") is planned for a Christmas 2021 release.  At least, that's the plan, such as it is.

 

As it should be apparent by now, these plans should be taken with a rather large helping of salt.  I may seem like a mild-manner programmer during the weekdays, but on my free time, I exercise my most impressive super-power:  procrastination.  More than a pro, I can castinate like a master! ?

 

I think I just got a little confused here, why are there different names for the updated Carol, will the new version be different other than corrective patches?  Will one of those titles ultimately replace the original when this is released or will v1.5 just be added to the main title.  I'm trying to figure out if the new version will be different enough to want to get the original game or is just game play fixes and the visuals be essentially the same.