next »

[dave]

cool, finished up half of the stage 2 implementation... also took a sec to add chat functionality to the webpage... figured it'd be nice to be a little more customer facing. rack ops time!

[st33d]

Putting in the help animations and tutorial.

Bar assembling all the levels into a campaign, I am right at the very end of 8 months of work.

This is my theme tune at the moment: http://listen.grooveshark.com/s/Dream+Is+Collapsing/2WYvo2

[dave]

[Ivan]

swords slicing through polygons like soft butter

[st33d]

polyunsaturated?

[bengrue]

Right now I'm implementing some cutscenes in a javascript jRPG enginey thing, and contemplating a DSL for the problem after using too many onCompletes.

[Mstrp]

Working on my Versus entry, recently finished a quadtree implementation on the server. Next up, unit abilities with some sort of buff/debuff tracking system. Never done anything like it before, looking forward to it.

[Glaiel-Gamer]

writing a std::list implemented as a deque to reduce memory allocations and improve locality of reference

here we are (it compiles and my game doesn't crash, which is good enough for now, notice any glaring errors?)

Code:

#ifndef GLA_PAGEDLIST_H
#define GLA_PAGEDLIST_H


#include <cstring>
#include <cstdlib>
#include "podvector.h"


namespace gla {
  template <typename T>
  class pagedlist {         //std::list implemented as a queue
    private:
      struct node {
        node* next; //if node is allocated, this points to the next one in the list
                    //if node isn't allocated, this points to the next free node in the list
        node* prev; //prev only applicable for allocated nodes
        //T data;

        char data[sizeof(T)]; //bytes for actual class data

      };
      struct page {
        page* next;
        gla::podvector<node> nodes;
        page(int size_):next(NULL),nodes(size_){}
      };
      page memory;
      node begin_;
      node end_;
      node* freelist;
      int size_;

      void addToFreeList(node& n){
        n.next = freelist;
        freelist = &n;
      }
      void page_init(page& mem){
        for(int i = 0; i<mem.nodes.size(); i++){
          addToFreeList(mem.nodes[i]);
        }
        mem.next = NULL;
      }
      node* alloc_node(){
        if(freelist == NULL){
          page* nextpage = &memory;
          while(nextpage->next) nextpage = nextpage->next;
          nextpage->next = new page(nextpage->nodes.size()*2);
          page_init(*(nextpage->next));
        }
        node* n = freelist;
        freelist = freelist->next;
        return n;
      }
      void freepage(page& mem){
        if(mem.next){
          freepage(*mem.next);
          delete mem.next;
        }
      }
    public:

      class iterator {
        friend class pagedlist<T>;
        private:
          node* n;
        public:
          iterator(node* n_=NULL):n(n_){}
          bool operator==(const iterator& rhs){return n==rhs.n;}
          bool operator!=(const iterator& rhs){return n!=rhs.n;}
          iterator operator++(){n=n->next;return *this;}                //preincrement
          iterator operator++(int){n=n->next;return iterator(n->prev);} //postincrement
          iterator operator--(){n=n->prev;return *this;}                //preincrement
          iterator operator--(int){n=n->prev;return iterator(n->next);} //postincrement
          T& operator*(){return *reinterpret_cast<T*>(n->data);}
          T* operator->(){return reinterpret_cast<T*>(n->data);}
      };


      pagedlist(int initial_page_size=8): memory(initial_page_size) {
        freelist = NULL;
        page_init(memory);
        begin_.next = &end_;
        begin_.prev = NULL;
        end_.prev = &begin_;
        end_.next = NULL;
        size_ = 0;
      }

      pagedlist(const pagedlist<T>& rhs): memory((8>rhs.size())?8:rhs.size()) {
        size_ = 0;
        freelist = NULL;
        page_init(memory);
        begin_.next = &end_;
        begin_.prev = NULL;
        end_.prev = &begin_;
        end_.next = NULL;

        node* n = rhs.begin_.next;
        while(n != &rhs.end_){
          push_back(*reinterpret_cast<T*>(n->data));
          n = n->next;
        }
      }

      pagedlist<T> operator=(const pagedlist<T>& rhs) {
        if(&rhs != this){
          clear();
          node* n = rhs.begin_.next;
          while(n != &rhs.end_){
            push_back(*reinterpret_cast<T*>(n->data));
            n = n->next;
          }
        }
        return *this;
      }


      void clear(){
        node* n = begin_.next;
        while(n != &end_){
          reinterpret_cast<T*>(n->data)->~T();
          n = n->next;
        }

        end_.prev->next = freelist;
        freelist = begin_.next;

        begin_.next = &end_;
        begin_.prev = NULL;
        end_.prev = &begin_;
        end_.next = NULL;

        size_ = 0;
      }

      ~pagedlist(){
        clear();
        freepage(memory);
      }

      void push_front(const T& data){
        node*n = alloc_node();

        n->prev = &begin_;
        n->next = begin_.next;
        begin_.next->prev = n;
        begin_.next = n;

        /**reinterpret_cast<T*>(n->data) = */new (n->data) T(data);
        size_++;
      }
      void push_back(const T& data){
        node*n = alloc_node();

        n->prev = end_.prev;
        n->next = &end_;
        end_.prev->next = n;
        end_.prev = n;

        /**reinterpret_cast<T*>(n->data) = */new (n->data) T(data);
        size_++;
      }

      void pop_back(){
        node* newend = end_.prev->prev;
        newend->next = &end_;

        reinterpret_cast<T*>(end_.prev->data)->~T();

        addToFreeList(*end_.prev);
        end_.prev = newend;
        size_--;
      }

      void insert(iterator pos, const T& value){
        node* posn = pos.n;
        node* prev = pos.n->prev;
        node* n = alloc_node();

        posn->prev = n;
        n->next = posn;
        n->prev = prev;
        prev->next = n;

        /**reinterpret_cast<T*>(n->data) = */new (n->data) T(value);


        size_++;
      }

      iterator erase(iterator pos){
        node* prev = pos.n->prev;
        node* next = pos.n->next;
        prev->next = next;
        next->prev = prev;

        reinterpret_cast<T*>(pos.n->data)->~T();
        addToFreeList(*pos.n);


        size_--;
        return iterator(next);
       
      }

      iterator begin() { return iterator(begin_.next); }
      iterator end() {return iterator(&end_); }

      T& back(){
        return *reinterpret_cast<T*>(end_.prev->data);
      }

     

      int size() const {
        return size_;
      }

      template <class Predicate>
      void remove_if(Predicate pred){
        iterator it = begin();
        while(it != end()){
          if(pred(*it)){
            it = erase(it);
          } else {
            ++it;
          }
        }
      }
  };
}



#endif

I only implemented functions my game uses so its only a partial implementation of std::list, but it will help keep list nodes mostly on the same page in memory

[BorisTheBrave]

No bugs, but a few nitpicks on performance and style:

It seems pretty similar to allocating your memory in slabs - it wouldn't be quite the same, but you could simply use the built in allocator support to do so.

node::data doesn't have the same alignment requirements as T does. Unlikely to go wrong, though.

freepage is recursive for some reason.

You never free pages except at the end. This would be ok, if it wasn't you are also doing exponential growth of page sizes. Those smaller pages are going to be a constant thorn in your locality problems, you really want it so that long term use with a bounded size eventually ends up on one page. You should at least free all but the largest page when clearing.

Potentially, large pages could be aligned on actual memory pages. I think this has some performance benefits.

You can use a raw pointer to an array instead of a vector, as you are not using nodes.size() anywhere, and save yourself a couple of bytes. For that matter, you should allocate page and the associated node list consecutively, this would avoid an additional allocation.

Default constructor does allocations - this should be avoided, as it's often unavoidable to default construct things when writing templated algorithms.

You use const T& when sometimes T would be more appropriate for some T. Type-trait that stuff.

[Glaiel-Gamer]

You never free pages except at the end. This would be ok, if it wasn't you are also doing exponential growth of page sizes. Those smaller pages are going to be a constant thorn in your locality problems, you really want it so that long term use with a bounded size eventually ends up on one page. You should at least free all but the largest page when clearing.

Potentially, large pages could be aligned on actual memory pages. I think this has some performance benefits.

You can use a raw pointer to an array instead of a vector, as you are not using nodes.size() anywhere, and save yourself a couple of bytes. For that matter, you should allocate page and the associated node list consecutively, this would avoid an additional allocation.

thanks for the pointers, as I said before this is meant to be specific to my game (most of the commonly-accessed lists are copy-constructed from level data which avoids the small-page problem) but I'll check these out at least.

[kefka]

I'm working on implementing a "context stack" (fancy words for a state machine) for my architecture.

My game loop basically looks like this:

Code:

context->input();
context->update();
context->draw();

And the application object allows you to:

Code:

pushContext(Context* c);
popContext();
swapContext();

I'm keeping Context as abstract as I can, it could be as something as simple as a menu overlay to the primary game world.  I havent decided how I would like to handle the simulation of multiple contexts, except embedding one as a child of the other, which I don't particularly like.

[Trent]

I'm setting up a 3D platformer in AS3, before Molehill comes out. I'd wait for Molehill but I need money now. 

[Nix]

A level editor/core engine for my game. Instead of having two distinct programs (a level editor and the game itself), I am programming the game such that all the components in the scene graph can be moved around and edited on the fly while the game is running, kind of like Super Meat Boy's devmode. Then the designer can save the current state of the level as the "default" that will be loaded in when the level is run by the player for the first time.

I haven't touched the code in about a week because I've been planning this all out on paper. Check out my sig if you want to follow the progress.

[Trent]

Check out my sig if you want to follow the progress.

Interesting. I've seen this project through DVGMusic (David Carney). Looking good so far! 

[kefka]

A level editor/core engine for my game. Instead of having two distinct programs (a level editor and the game itself), I am programming the game such that all the components in the scene graph can be moved around and edited on the fly while the game is running, kind of like Super Meat Boy's devmode. Then the designer can save the current state of the level as the "default" that will be loaded in when the level is run by the player for the first time.

I haven't touched the code in about a week because I've been planning this all out on paper. Check out my sig if you want to follow the progress.

Awesome.  This is exactly what i'd like to do for my game.  Editor is just running the game but with added functionality (the ability to edit data!).

Thanks for sharing, I will definitely take a glance at your work