Thread: Internal representation of Pacman-style maps

  1. #1
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229

    Internal representation of Pacman-style maps

    Just wondering, how are maps in games like Pacman represented internally? Is it in tiles? Wouldn't it be difficult if objects move at different speeds? What about collision detection (with objects between tiles)?

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> Just wondering, how are maps in games like Pacman represented internally? Is it in tiles? Wouldn't it be difficult if objects move at different speeds? What about collision detection (with objects between tiles)?

    That's an odd question! I don't know though, as I've never seen the source. If you're up to it this site supposedly has the assembly language code to the original game. Have fun.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    hahaha that's a bit too much fun for me to consume at this moment. I'm looking more for the way people generally do things like this, not particularly what they did in Pacman.

  4. #4
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    Well, it could easily be done in a number of ways. Tilemap could certainly be one of them. Tiles dont really have anything to do with speeds really, all that is programmed later. A tilemap is basically just a 2D array to store data, it can range from extremely simple which holds just a coordinate and texture data to really complex and hold all sorts of things such as collision etc.
    Also, most map editors like for example let you add collision data and load a map straight into the game. But the concept is still the same. Heres a great map editor I have used for my past projects - Mappy

  5. #5
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,273
    I think that Pacman was generally using the idea of a fixed-dimension grid onto which the map is generated (from fixed patterns in this case, but could be made random with some additional logic), then sprite movement/collision was done in the usual x-y coordinates with conversion of map elements to these coordinates as necessary.

    I had an idea to try and write a graphical Pacman in x86 assembly so that it would fit in the boot sector of a floppy disk; I didn't quite manage it but I may have another stab and see if a simple compression routine will fix my problem.

  6. #6
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Haha I see. Thanks!

    Pacman in boot sector sounds awesome! Better finish it before floppies go completely extinct, though. Boot sector on a CD-ROM doesn't sound half as cool .

  7. #7
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Not sure how Pacman did it but how I would do it (based off a real maze problem) as a first attempt:
    Since the maze is of a fixed dimension with walls only able to be placed at discrete spots what you can do is create an array for horizontal walls and an array for vertical walls. Each cell has a X and Y value that you can use to get the index for the arrays. The arrays are simply boolean flags that tell you if the wall is present.

    To handle different "speeds" you can do frequency division using a master clock to control the timing.

  8. #8
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Ah thanks! I think I get it now.

  9. #9
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    I was just thinking about this. Because Pacman is not a maze solver, maybe it makes more sense to not worry about representing walls as cells. Perhaps just have a array - a linked list of legally traversable cells with some sort of multiple branching at the intersect points. After all you don't need to check whether you're attempting to make a 90 degree turn into a wall. But it's been a long time since I played Pacman, if at all.

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I believe Pacman was probably using pre-drawn graphics tiles for the entire screen. As for the internal storage of the data you could pack it all into an array. The food and pills would probably be stored and drawn differently than the rest of the map. I would imagine the map tiles do not have the food drawn in them but rather might have a list of x,y coordinates indicating where the food goes and perhaps another variable indicating what type of food it is.

    The tile approach would also mean you could probably pack an entire row of the map in one integer or one BCD of a set length. You could also RLE the rows to make them even smaller.
    I would imagine you could store many many maps of set size in ROM this way. A lot of the tiles used also were repeated but their color 'schemes' were altered to fit the level.

    Once you get the memory rep done the rest is easy.

    Code:
    ...
    ...
    int row = Pacman_y / cellSize;
    int col = Pacman_x / cellSize;
    
    int offset = row * width + col;
    int result = Level[offset];
    
    if (result == FOOD)
    {
       //Chomp the food
       Level[offset] = EMPTY;
       EatFood();
    }
    else if (result == PILL)
    {
      //Pill chomped - set eat ghost mode
      EatPill();  
    }
    else if (result == GHOST)
    {
       if (GetGameState() != EAT_GHOSTS && !Pacman_invulnerable)
       {
           KillPlayer();
       }
    }
    else if (result == CHERRY)
    {
       //Chomped a cherry
    }
    ...
    ...
    The game logic is actually very easy and you could probably do the entire game without any expensive hit detection code.
    Last edited by VirtualAce; 07-27-2009 at 07:02 PM.

  11. #11
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by nonoob View Post
    I was just thinking about this. Because Pacman is not a maze solver, maybe it makes more sense to not worry about representing walls as cells. Perhaps just have a array - a linked list of legally traversable cells with some sort of multiple branching at the intersect points. After all you don't need to check whether you're attempting to make a 90 degree turn into a wall. But it's been a long time since I played Pacman, if at all.
    I don't think using a list of adjacent cells would be very good in this case as direction still matters for moving pacman. If pacman is moving up then you need to know if the up direction is a valid move or not.


    Quote Originally Posted by Bubba View Post
    I believe Pacman was probably using pre-drawn graphics tiles for the entire screen. As for the internal storage of the data you could pack it all into an array. The food and pills would probably be stored and drawn differently than the rest of the map. I would imagine the map tiles do not have the food drawn in them but rather might have a list of x,y coordinates indicating where the food goes and perhaps another variable indicating what type of food it is.

    The tile approach would also mean you could probably pack an entire row of the map in one integer or one BCD of a set length. You could also RLE the rows to make them even smaller.
    I would imagine you could store many many maps of set size in ROM this way. A lot of the tiles used also were repeated but their color 'schemes' were altered to fit the level.

    Once you get the memory rep done the rest is easy.

    The game logic is actually very easy and you could probably do the entire game without any expensive hit detection code.
    While the drawing of the maze could be done with pre-drawn graphics you'd still need to have some sort of representation of the maze to determine valid moves.

  12. #12
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    I'd probably scratch RLE from that, Bubba. The original was done in assembler and I believe occupied 24k of memory over six 4k roms (search for puckman, choose Japan Set 1, the original). The overhead for RLE encoding/decoding wouldn't compensate the gain in storage since everything must reside in memory.

    I've been doing some Z80 programming (exactly where puckman, the original, was developed) and have been gaining a lot of respect for the work these folks done back then. The amount of assembly optimization necessary was astounding.

    Packman map could have been stored as a bitfield emulating a grid with the minimum resolution necessary for representation. The map was only concerned with walls and empty space, since dots were almost certainly dealt with by some other routine tied to the game loop. The map is also symmetrical on the vertical axis, so I would definitely only want to store half of it and generate the other half.

    Since the map is entirely made up of lines, I seem to think it would be cheaper to draw it programmatically, instead of storing pre-drawn graphics. The bitfield would hold its representation for all routines involved.
    Last edited by Mario F.; 07-27-2009 at 09:12 PM. Reason: added link to maws
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  13. #13
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Quote Originally Posted by Thantos View Post
    I don't think using a list of adjacent cells would be very good in this case as direction still matters for moving pacman. If pacman is moving up then you need to know if the up direction is a valid move or not.
    I'm not saying adjacent cells. Just all cells that are playable are in a linked list. If "up" is a valid direction then those cells are traversed on the list at the time. The entire list is a 1-dimensional array with branch points represented by a node index value. Seems feasible to me.

  14. #14
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Linked list is totally out of the question for older systems. I would agree with the bitfield approach but the max you would get was 8 bits back then.

  15. #15
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Bleh, I would have hated being a programmer back then. Having to squeeze every last drop of optimization out of it at the expense of writing maintainable code. Depressing.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BN_CLICKED, change button style
    By bennyandthejets in forum Windows Programming
    Replies: 13
    Last Post: 07-05-2010, 11:42 PM
  2. Replies: 2
    Last Post: 01-06-2009, 10:37 AM
  3. WM_CAPTION causing CreateWindowEx() to fail.
    By Necrofear in forum Windows Programming
    Replies: 8
    Last Post: 04-06-2007, 08:23 AM
  4. Button handler
    By Nephiroth in forum Windows Programming
    Replies: 8
    Last Post: 03-12-2006, 06:23 AM
  5. Tab Controls - API
    By -KEN- in forum Windows Programming
    Replies: 7
    Last Post: 06-02-2002, 09:44 AM