Thread: Game programming task

  1. #1
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607

    Game programming task

    http://www.suckerpunch.com/joblist.p...Programmer.txt

    Check out the requirement at the bottom of the page. Sounds easy enough eh?

    One problem. Since they do not allow you to use malloc, new or a simple STL queue and yet want you to destroy the memory - how do you do this?

    The memory they are showing is created on the stack. Therefore calling destroy on the queue will do....um....nothing. You can't destroy it. Only thing you can do is flag the queue as being invalid and unusable.

    Comments? The problem itself is quite easy. But I'm not understanding the destroyQ() function. Doesn't make sense.

    The C++ version they are asking for is so simple. Just use the STL.

    EDIT:Ahhh...destroyQ() is simply destroying the pointer.
    Any takers?

    Why not do a contest that could land you a job eh?
    Last edited by VirtualAce; 12-05-2005 at 02:37 AM.

  2. #2
    ---
    Join Date
    May 2004
    Posts
    1,379
    It's probably over my head
    It would be a good problem to do for experience and I would love to try it if I had more time on my hands

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Well I'm working on an MFC version that does all of the work behind the scenes.

    Here is my setup.

    QueueInfo
    • holds information about 1 queue
    • TOQ = top of queue
    • BOQ = bottom of queue
    • Size = total size of queue (BOQ-TOQ)
    • ID = for easy access
    • Active = indicates this Queue has been created and is valid


    QueueSystem
    • has an array of 64 QueueInfo structures
    • has a 2048 BYTE array used as the 'shared' memory area


    When you enQ (push) or deQ (pop):
    • The enQ function matches the ID in QueueInfo parameter with known QueueInfo information
    • enQ calls QueueSystem::UpdateQueueInfo() and passes the ID of the queue and the change amount.
    • QueueInfo TOQ,BOQ, and Size are updated to reflect new changes - but only queues following the supplied Queue ID are updated. In other words since the data is like a bunch of mini-stacks, if you are pushing, popping on Queue 5 - then Queues 4,3,2, and 1 will not be bothered at all. So the worst case scenario is doing operations on Queue 1. The higher in the stack you perform an operation, the worse the performance is.
    • QueueSystem::UpdateQueueInfo calls QueueSystem::UpdateQueueData
    • Since the final data is really just a small array of bytes, performing a bubble sort on the data from QueueSystem::TotalSize to index (the place where data is being pushed or popped) will maintain data integrity. The QueueInfo structures have already been updated to reflect this change


    When you create a Queue:
    • The new Queue is placed following the last active Queue.
    • No updating of existing data is required.
    • Will bail if no room for new queue
    • returns a QueueInfo structure describing the Queue


    When you destroy a Queue:
    • Checks to make sure supplied Queue is active, bails if not
    • Zeroes out Queue::Data[] from QueueInfo::TOQ to QueueInfo::BOQ
    • Sets active flag to false and zeroes out members in QueueInfo
    • Reduces number of active queues
    • Preserves index of next queue


    So a data queue might look like this:

    Queue1
    ----------
    0 5 6 7 8 10

    Queue2
    ----------
    1 2 3 4

    The actual data array would look like this
    0 5 6 7 8 10 1 2 3 4

    You are basically just doing operations on the array. The Queues just store the starting and ending indexes in the array for that particular Queue.

    Simple, but cryptic in C.
    C++ would be much better.

    Now off to test my theories. I'm sure I've overlooked something.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    847
    Code:
    unsigned char data[2048];
    This array is your heap. You need to implament your own memory managment functions for allocating/freeing memory from that byte array. destroyQ() should not only delete the que pointer but also ensure that the memory used by the que is free'ed.

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Well not actually. The problem states that you will never have more than 64 queues. So I've created 64 queues, but they are not all active. The only way to access the data is through a QueueInfo structure. So if the active flag is false the function will call onIllegalOperation(). There is no need to de-allocate anything. You have 2048 bytes at your disposal. Now you could re-allocate different sizes and resize the array but I don't think that's what they want. In essence the memory is being 'free'ed' because the destroyQ() function zeroes out the memory and it also takes the TOQ member from the QueueInfo of the Queue being destroyed and sets that as the next available index into the data array. This method is much faster than actually resizing the array.

    I'm just keeping track of indices into the data array and storing that info in a structure.

    I'm using the ID so that I can update all QueueInfo's affected by a data operation by simply iterating from ID to TotalSize in the QueueInfo array.

    This is similar to methods I use in game programming where I allocate one huge chunk of memory and use that during the game for what I need. I just keep track of the memory start location, end location, chunk size, chunk ID, etc.

    EDIT: So far it works perfect.
    Last edited by VirtualAce; 12-05-2005 at 05:29 AM.

  6. #6
    ---
    Join Date
    May 2004
    Posts
    1,379
    Well if I actually had to implement my own malloc() I wouldn't even know where to start.

  7. #7
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I don't think they are asking that in this question. The only thing that is bothering me is this:

    Q * createQ();

    Where Q can be any data type. Problem here is since you cannot create Q on the heap, Q must be created on the stack. So my implementation is more:

    Q createQ();

    You can't do this:

    Code:
    Q* createQ(void)
    {
      Q newQ;
      //set data members here
    
      return &newQ;
    }
    It compiles but you are returning a reference to a temporary. newQ goes out of scope and yet you return a reference to it. Bad idea.

    And you can't do this:

    Code:
    Q* createQ(void)
    {
      Q *newQ=new QueueInfo();
      ...
      return newQ;
    }
    Because you can't use the heap. So in my version I'm still returning a pointer, but it's on the stack. I think it returns in EAX first and then pushes EAX to the stack. I dunno the exact C++ assembly implementation in the compiler.

    If they want me to use the data array to also act as a memory heap for the structure then I have a bit more coding to do. However I don't think this is the case since they only allow 2048 bytes but yet want to support at least a dozen queues and a max of 64. Do the math and you will find out that 2048 bytes would not be enough to hold essential queue information and queue data for 12 different queues, much less 64.

    I'm also wondering if they are allowing 2048 bytes per queue and do not want the queues to share memory. My implementation is that all queues use the same array, just different sections of it. So far it works perfect and each queue can grow to any size it wants, as long as the total size of the data is <=2048 bytes. I'm having a bit of a small problem with queues farther down in the array not having their data sorted correctly to account for changes, but I'm sure it's something simple.

    My version uses MFC as a front end interface so I'm not sure they would even accept my code - or perhaps they would be impressed by the GUI portion and demonstration of MFC knowledge and hire me. Hah. Right.

    I really just put it here as an exercise for us to do. It's a real world problem and I figured it would be good practice.

    No structures - pack 2 DWORDs
    Now I could get really funky with the QueueInfo and pack all of it's info in 8 bytes.

    TOQ - top of queue (2 bytes)
    BOQ - bottom of queue (2 bytes)
    Size - max size can be 2048 so need 2 bytes here, even though most queues will NOT be 2048 bytes.
    ID - 1 byte (max of 64 - can be represented in one byte
    Active flag - 1 bit (true or false)

    So the compression would look like this:

    DWORD InfoHigh;
    DWORD InfoLow;

    InfoHigh
    * bits 0 to 15 = TOQ
    * bits 16 to 31= BOQ

    InfoLow
    * bits 0 to 15 = Size
    * bits 16 to 23 = ID
    * bit 24=Active flag

    And I'd have 7 bits of wasted space.

    The overall size though would prob be the same as my structure size if I use pragma(1).

    I could code this, but I don't think it's what they want.

    Your own malloc and free
    Coding your own malloc would not be that hard provided you made some limitations to it.

    1. Chunks cannot be resized.
    2. Chunks cannot be shared.
    3. When a chunk is de-allocated or free'd the information about that chunk is still available. When a new chunk is requested, the system would check the recently de-allocated chunk(s) to see if the new chunk would fit. This would minimize the search for a suitable chunk. De-allocated chunks should be kept in an array. It wouldn't need to be that large to be an effective chunk cache.

    Resizing chunks is a mess because you must move other chunks, etc.
    Sharing chunks is messy because you run into a lot of data integrity and data bounds problems. You don't want to run into someone else's data even though it's still inside of your chunk.
    Last edited by VirtualAce; 12-06-2005 at 06:57 AM.

  8. #8
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    I know this is an old thread, but I just found it and felt like implementing my own solution.
    Code:
    #include <iostream>
    using namespace std;
    
    ////////////////////////////////////////////////////////////////////////////////
    
    typedef unsigned char uchar;
    typedef unsigned long Q;
    
    ////////////////////////////////////////////////////////////////////////////////
    
    // we use an array of Q to manage the shared queue memory; each
    // element can be composed of 3 units:
    // |-|-------|--------|
    // | |       |        |
    // |-|-------|--------|
    //  ^ ^       ^-- 8 bits: offset to next item in this queue
    //  | |-- 7 bits: queue ID
    //  |-- 1 bit: used by root of queue
    //             set if item has been popped, unset if item
    //             content is valid
    
    struct QMan {
      enum { MEMORY_SIZE = 2048            };
      enum { FIRST_ITEM  = MEMORY_SIZE     };
      enum { LAST_ITEM   = MEMORY_SIZE + 1 };
    
      static uchar  data[MEMORY_SIZE];
      
      static Q      q_info[MEMORY_SIZE];
      static short  used_slots;
      static Q      *end;
      
      // print all data about each item in shared queue memory
      static void print_all() {
        for (int i = 0; i < MEMORY_SIZE; ++i)
          cout << "[" << i << "] = " << ((q_info[i] & 0x80000000) >> 31) << ", " << 
            ((q_info[i] & 0x7FFF0000) >> 16) << ", " << (q_info[i] & 0x0000FFFF) << 
            ", value = " << (short)data[i] << endl;
        cout << endl;
      }
    
      // find the first free slot starting from qitem_start
      // (looping around if necessary)
      static Q* get_first_free(Q *qitem_start = 0) {
        Q *q        = qitem_start;
        Q *lastitem = end;
        
        if (qitem_start == 0)
          q = q_info;
        
        if (*q == 0)
          return q;
          
        while (*++q > 0) {
          if (q == lastitem) {
            if (qitem_start > q_info) {
              q = q_info;
              lastitem = qitem_start;
            }
            
            return 0;
          }
        }
        
        return q;
      }
      
      // all slots are free
      static bool is_empty() {
        return used_slots == 0;
      }
      
      // all slots are used
      static bool is_full() {
        return used_slots == MEMORY_SIZE;
      }
      
      // index of queue item
      static int get_index(Q *qitem) {
        return qitem - q_info;
      }
      
      // this modifies only the root
      static void set_root_popped(Q *qitem, bool is_popped = true) {
        if (is_popped)
          *qitem |= 0x80000000;
        else
          *qitem &= ~0x80000000;
      }
      
      // true if root item has been popped and is not the first
      // valid item in the queue
      static bool get_root_popped(Q *qitem) {
        return (*qitem & 0x80000000) != 0;
      }
      
      // set the queue id
      static void set_qid(Q *qitem, short qid) {
        *qitem &= 0x8000FFFF;
        *qitem |= 0x7FFF0000 & (qid << 16);
      }
      
      // retrieve queue id
      static short get_qid(const Q *qitem) {
        return (*qitem & 0x7FFF0000) >> 16;
      }
      
      // the offset is the number of elements to the next item
      // in this queue; set to FIRST_ITEM if root is available
      // but unset; set to LAST_ITEM if item is the queue's tail
      static void set_offset_to_next(Q *qitem, short offset) {
        *qitem &= 0xFFFF0000;
        *qitem |= 0x0000FFFF & offset;
      }
      
      // retrieve the offset to the next
      static short get_offset_to_next(const Q *qitem) {
        return *qitem & 0x0000FFFF;
      }
    } q_man;
    
    ////////////////////////////////////////////////////////////////////////////////
    
    uchar QMan::data[]      = { 0 };
    Q     QMan::q_info[]    = { 0 };
    short QMan::used_slots  = 0;
    Q     *QMan::end        = q_info + QMan::MEMORY_SIZE;
    
    ////////////////////////////////////////////////////////////////////////////////
    
    Q*            createQ();                  // Creates a FIFO byte queue, returning a handle to it.
    void          destroyQ(Q *q);             // Destroy an earlier created byte queue.
    void          enQ(Q *q, unsigned char b); // Adds a new byte to a queue.
    unsigned char deQ(Q *q);                  // Pops the next byte off the FIFO queue.
    
    ////////////////////////////////////////////////////////////////////////////////
    
    void onOutOfMemory() { cout << "\nOut of Memory" << endl; }
    void onIllegalOperation() { cout << "\nIllegal Operation" << endl; }
    
    ////////////////////////////////////////////////////////////////////////////////
    
    int main() {
      Q * q0 = createQ();
      enQ(q0, 0);
      enQ(q0, 1);
    
      Q * q1 = createQ();
      enQ(q1, 3);
      enQ(q0, 2);
      enQ(q1, 4);
    
      printf("%d", deQ(q0));
      printf("%d\n", deQ(q0));
      
      enQ(q0, 5);
      enQ(q1, 6);
    
      printf("%d", deQ(q0));
      printf("%d\n", deQ(q0));
      
      destroyQ(q0);
      
      printf("%d", deQ(q1));
      printf("%d", deQ(q1));
      printf("%d\n", deQ(q1));
      
      destroyQ(q1);
    
      return 0;
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    
    Q* createQ() {
      if (q_man.is_full()) {
        onOutOfMemory();
        return 0;
      }
      
      Q *pQ = q_man.get_first_free();
      
      if (pQ == 0) {
        onOutOfMemory();
        return 0;
      } 
        
      // increment the number of used slots
      ++q_man.used_slots;
      
      // set the id of this new queue item
      q_man.set_qid(pQ, q_man.get_index(pQ) + 1);
      
      // set the offset to the next item denoting
      // that the root is the last item
      q_man.set_offset_to_next(pQ, QMan::FIRST_ITEM);
      
      return pQ;
    }
    
    void destroyQ(Q *q) {
      // no queues to destroy
      if (q_man.is_empty()) {
        onIllegalOperation();
        return;
      }
      
      // the specified queue is invalid; it does
      // not contain a queue id
      if (q_man.get_qid(q) == 0) {
        onIllegalOperation();
        return;
      }
      
      while (true) {
        // decrement used item count
        --q_man.used_slots;
        
        // retrieve the offset to the next item (of course,
        // this may be negative)
        short offset = q_man.get_offset_to_next(q);
        
        // free up the slot for other queues to use
        *q = 0;
        
        // the last item in the queue (it does not have
        // an offset to the next item)
        if (offset == QMan::LAST_ITEM)
          break;
        
        q += offset;
      }
    }
    
    void enQ(Q *q, unsigned char b) {
      short offset = q_man.get_offset_to_next(q);
      
      // the root has been popped and there are no other
      // items in the queue; make it available again
      if (q_man.get_root_popped(q) &&
          q_man.get_offset_to_next(q) == QMan::LAST_ITEM)
        q_man.set_root_popped(q, false);
      // the root is not empty
      else if (offset != QMan::FIRST_ITEM) {
        // find the last item in this queue
        while (true) {
          short offset = q_man.get_offset_to_next(q);
          
          if (offset == QMan::LAST_ITEM)
            break;
            
          q += offset;
        }
        
        // there are no free slots; exit
        if (q_man.is_full()) {
          onOutOfMemory();
          return;
        }
        
        // we have a free slot to add an item
        Q *pQ = q_man.get_first_free(q);
        
        // insure we really retrieved a free item
        if (pQ == 0) {
          onOutOfMemory();
          return;
        }
    
        // set the queue id for the new item
        q_man.set_qid(pQ, q_man.get_qid(q));
    
        // set the offset from the previous item to the new item
        q_man.set_offset_to_next(q, pQ - q);
        
        // point at the new item
        q = pQ;
      }
      
      // set the value for the current item
      q_man.data[q_man.get_index(q)] = b;
      
      // set the offset to a unique value, so we
      // know it has been used, but is not pointing
      // to a next item
      q_man.set_offset_to_next(q, QMan::LAST_ITEM);
    }
    
    unsigned char deQ(Q *q) {
      unsigned char value = 0;
      
      short offset = q_man.get_offset_to_next(q);
      
      // if we have previously popped the root item, pop
      // the next item; we handle it this way so a dequeue
      // occurs in constant time (as opposed to copying all
      // the items down and deleting the last)
      if (q_man.get_root_popped(q)) {
        // there are no items in this queue
        if (q_man.get_offset_to_next(q) == QMan::LAST_ITEM)
          onIllegalOperation();
        else {
          Q *next = q + offset;
          
          // get the value of the first valid item
          value = q_man.data[q_man.get_index(next)];
          
          // calculate the offset from the root to the new next
          // valid item (the one after the popped item)
          short offset_next = q_man.get_offset_to_next(next);
          
          // there are no more items
          if (offset_next == QMan::LAST_ITEM)
            q_man.set_offset_to_next(q, QMan::LAST_ITEM);
          // do the calculation
          else
            q_man.set_offset_to_next(q, offset + offset_next);
            
          // free the popped item
          *next = 0;
        }
      }
      else {
        // get the value for the root item
        value = q_man.data[q_man.get_index(q)];
        
        // now set it as popped
        q_man.set_root_popped(q);
      }
      
      return value;
    }

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Nice I still have my MFC version as well. It has one bug where the memory is not rotated correctly when something is removed, but not hard to fix.

    After working on this code I cannot see why they want something like that. Maybe to see if you can think through it. Most of it is not about understanding tech or anything about the language, it's about trying to get the thing working with limited resources. I'm sure all of us here on the board if given enough time could do this problem.

    It's not hard at all.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how do the game engine and the api interact?
    By Shadow12345 in forum Game Programming
    Replies: 9
    Last Post: 12-08-2010, 12:08 AM
  2. game engine advice?
    By stien in forum Game Programming
    Replies: 0
    Last Post: 01-23-2007, 03:46 PM
  3. 2D RPG Online Game Project. 30% Complete. To be released and marketed.
    By drallstars in forum Projects and Job Recruitment
    Replies: 2
    Last Post: 10-28-2006, 12:48 AM
  4. Scheduling Algo
    By BigDaddyDrew in forum C++ Programming
    Replies: 41
    Last Post: 03-08-2003, 11:00 AM
  5. My Maze Game --- A Few Questions
    By TechWins in forum Game Programming
    Replies: 18
    Last Post: 04-24-2002, 11:00 PM