FOV

I’ve been coding a little roguelike this past week and I just got around to looking at FoV algorithms. Now, many of these algorithms I found hard to understand, but after some trial and error I figured out an easy way (in my mind!) for it to work. Now I’m curious, has anyone else used this technique too? I didn’t see it listed on roguebasin.

Conceptually, it is an optimization over a method that traces hundreds of rays from the player outward. Instead of tracing the rays while the game is running, the work is done beforehand and stored in a static lookup table. The in-game algorithm does a few bitwise operations on the table to determine which rays have been blocked.

The set of rays used to generate the lookup table determine how your FoV looks. Originally, my rays were straight lines from the center to perimeter coordinates. While this may seem sufficient, the results were actually rather ugly and contained artifacts. There were too many squares being marked unseen in unreasonable places. What I needed was permissive FoV. To do this, I used a modified version of Bresenham’s line algorithm that iterated every possible line and sub-line that I cared about. This turned out to work perfectly.

Here’s a few comments I wrote in the source file. Sorry if my explanations are bad; if you want to see the source code, perhaps I’ll make it publicly available on Bitbucket.

// This file generates a lookup table for a fast permissive field of view
// algorithm.
//
// The table is in the octant shaded by '#':
// +-x------>
// y\########
// | \#######
// |  \######
// |   \#####
// v    \####
//
// A higher-level description of the algorithm is as follows:
// We begin by finding every unique "ray" in the octant.
// The rays start at the origin and emanate outwards.
// We give each ray a unique index number to identify it.
// Then, for every coordinate that the ray passes through, we add the ray's
// index to a set belonging to that coordinate.
//
// Finding the LOS is easy with this array of sets: Iterate every coordinate
// in the the octant starting from the center and moving outwards.
// If the coordinate contains a wall, look at what rays belong in its set.
// Since you are iterating outwards, you now know that every ray in that
// set will be blocked in future iterations too. Thus, every ray in that
// set can be considered "dead". Now, for future iterations, the "live"
// rays of a coordinate will be the set belonging to the coordinate _minus_
// the set of previously iterated "dead" rays. If a coordinate has zero "live"
// rays, then it will not be visible.
//
// In practice, this algorithm can be done efficiently using bitwise
// operations. Each ray is given a unique bit flag, and each coordinate set
// is represented by the bitwise OR of every passing ray's flag.
// Calculating the LOS uses bitwise 'AND's to compare "dead" rays to "live"
// rays.

Note: I looked at DCSS’s FoV code quite a bit before doing this, but I couldn’t grok it. I do know it involves lots of precomputation though. Perhaps it’s the same as my version?

Posted in Programming | Leave a comment

Multi-step iterators using coroutines.

I wanted to turn this multi-step iteration function into an iterator:

template<typename Func>
void iterate_edges(rect r, Func func = Func())
{
    coord current = r.c;
    for(;current.x < r.rx(); ++current.x)
        func(current);
    for(;current.y < r.ry(); ++current.y)
        func(current);
    for(;current.x > r.c.x; --current.x)
        func(current);
    for(;current.y > r.c.y + 1; --current.y)
        func(current);
}

It turns out that it can be done very simply using boost::asio::coroutine:

rect_edge_iterator& rect_edge_iterator::operator++()
{
    reenter(m_coro)
    {
        while(m_current.x < m_rect.rx())
        {
            ++m_current.x;
            yield return *this;
        }
        while(m_current.y < m_rect.ry())
        {
            ++m_current.y;
            yield return *this;
        }
        while(m_current.x > m_rect.c.x)
        {
            --m_current.x;
            yield return *this;
        }
        while(m_current.y > m_rect.c.y + 1)
        {
            --m_current.y;
            yield return *this;
        }
        --m_current.x; // change to an 'end' position
    }
    return *this;
}

I thought that was kind of neat. It’s not very often I find a practical use of stackless coroutines in C++.

Note: This only works cleanly for forward iterators.

Aside | Posted on by | Tagged | Leave a comment

The words “Design” and “Art” are suffixes.

Take a quick look at these definitions of “design” and “art”:

DesignThe process before creation.
ArtSomething intended to be aesthetically pleasing.

Notice how generic and nondescript these words are. They’re intended to group several similar things, rather than describe a single action.

Unfortunately, not everyone understands this. It’s quite often I see people use the words “design” and “art” to make sweeping generalizations about very specific branches of those topics. Even worse, the more vague one of these statements is, the more acclaim it receives!

artdesigntruth

Please, if you want to discuss “art” and “design” objectively then qualify them with another word. Be explicit and spell out what you mean, such as “graphic design”, “web design”, “software design”, etc.

If you want to linkbait then continue using the words ambiguously. For example, “10 tips for design”, “Why design is hard”, and “Video games considered art” are some great titles for your next blog post. You’ll come off as being deep and knowledgeable while saying nothing of meaning!

Posted in Uncategorized | Leave a comment

Stack-based template metaprogramming in C++ (11)

Many months ago right after G++ 4.7 was released I discovered a nifty syntax for writing metaprograms using a stack language similiar to Forth and Factor. I started writing a small library around it, but got sidetracked and never finished it. The following is an explanation and code.

Preliminary reading

http://factorcode.org/ is a great place to learn stack language programming and can be used as a reference when implementing words.

Rationale

Here’s a short, contrived example of a traditional metafunction (such as from Boost MPL) that computes the number of elements in a container that satisfy a predicate, squares the result, and then adds 5:

template<typename Predicate, typename List>
struct foo
: add<
      square<
          typename length<
              typename filter<
                  Predicate, List
              >::type
           >::type
      >::type,
      int_<5>
  >
{};

Yeah, that sucks.

Now compare it to a stack-based approach which was working code in my library:

struct foo : word<filter, length, square, int_<5>, add> {};
// alternate syntax:
using foo = word<filter, length, square, int_<5>, add>;

The difference is light and day! And if you make a mistake the errors are nicer too! I recall getting it down to a static assert message that contained the type of error and current stack which was infinitely more readable than the 10000 page garbage standard TMP spits out.

So how is this implemented?

The Stack

First off, let’s start out with implementing a stack using TMP. Stack languages use the stack for storing data.

The simplest way is to use variadic templates. A stack with ‘foo’ on top and ‘qux’ on the bottom can be represented as the following using variadic templates:

stack<foo, bar, qux>

In addition, we need to be able to push, pull, and get the top of the stack in order to use it.

Here is the full implementation:

template<typename...>
struct stack;
template<typename X, typename... Xs>
struct stack<X, Xs...> {
  using type = stack;
  using top = X;
  
  template<typename T>
  using push = stack<T, X, Xs...>;

  using pop = stack<Xs...>;
};
template<>
struct stack<> {
  using type = stack;

  template<typename T>
  using push = stack<T>;
};

(Note that templates aliases are used for the push/pop/top functions. This is because I find it to be more convenient than templated structs with a type member.)

Unfortunately, this stack has a minor problem notation-wise; languages like Factor position the top of the stack on the right while our notation positions it on the left. While this has no effect on the semantics of the program, it can be confusing to use. Luckily, the evaluator can use any type of TMP stack that supports push, pop, and top and so it is possible to write TMP stacks that notate the top of the stack on the right, although that is beyond the scope of this article.

Let’s also write a few helper functions that operate on our stacks as they’ll be needed later:

// pops N times from Stack
template<typename Stack, int N>
struct stack_drop {
  using type = typename stack_drop<typename Stack::pop, N - 1>::type;
};
template<typename Stack>
struct stack_drop<Stack, 0> {
  using type = Stack;
};

// returns top after popping N times from Stack
template<typename Stack, int N>
struct stack_index {
  using type = typename stack_index<typename Stack::pop, N - 1>::type;
};
template<typename Stack>
struct stack_index<Stack, 0> {
  using type = typename Stack::top;
};

Evaluation Groundwork

Implementing evaluation is where things get tricky. First off, let’s talk about words.

A ‘word’ in stack languages is essentially the functions that make up the program, and thus the input words compose the program code. In fact, the way words are implemented is just as metafunctions – they input a stack and output stack.

Words will be represented abstractly – a type that contains an apply metafunction can be used as a word. Here’s the pattern you’ll see:

struct {
  template<typename Stack>
  struct apply { // apply the stack to this word
    // ??
  };
};

One way of constructing words is through word composition. Given a list of words, composing them involves piping the output stack of the previous word as the input to the next, thus creating a new word which sends its input to the first word of the composition, and returns the result of the final word.

Here’s the skeleton of the implementation:

// word composition
template<typename... Words>
struct word {
  template<typename Stack>
  struct apply {
    // ??
  };
};

Word composition is crucial to creating stack programs. In fact, a stack program is just a composition of words!

Because of this, our eval function will have a word and a stack as parameters, with another stack being returned. Here’s the skeleton:

template<typename Word, typename Stack = stack<>>
struct eval {
  using stack = // ??
};

The stack defaults to an empty stack for convenience.

Here’s how it’s used:

eval<foo_word, stack<>>::stack

Complete Evaluator

Our groundwork is done, now onto the actual implementation.

Let’s first talk about implementing word composition.

A simple method of composing a list (which I did not use) involves realizing that words and composition form a monoid. The binary operator simply composes two words, and the identity word is just a word that returns its stack unchanged. Because of this, we can compose a list of words by folding the binary composition over the list.

Accidentally, however, I took a different path of implementation which I now realize is more powerful. The basis requires redefining word application to include another parameter – the list of words that come after the word being evaluated. For instance, if you’re evaluating this list:

[foo, bar, qux]

Then the list [bar, qux] would be applied to foo, which then applies [qux] to bar, and then [] to qux.

Those familiar with continuation passing style will see the similarity!

Here’s the new skeleton:

template<typename... Words>
struct {
  template<typename Stack>
  struct apply {
    template<typename... Remaining>
    struct continuation {
      // ...
    };
  };
};

I’m using the term continuation and remaining as those are the closest terms I can think of. Keep in mind that it’s referring to the remaining words of the composed list, not of the entire program. Thus, it forms what I’ll call (probably mistakenly) a scoped continuation.

Let’s start out implementing the simplest word we can think of: the identity word. As said early, the identity word returns its stack unchanged. While this may seem useless, we can actually use it as a starting point to create other words.

Here’s the code:

struct id {
  template<typename Stack>
  struct apply {
    // This only catches the empty list - specialization will catch others
    template<typename...>
    struct continuation {
      using stack = Stack;
    };

    template<typename Word, typename... Remaining>
    struct continuation<Word, Remaining...> {
      using stack =
        typename Word::template apply<Stack>
        ::template continuation<Remaining...>::stack;
    };
  };
};

This has two behaviors:
- The resulting stack with an empty continuation/remaining list is simply the stack passed as an argument
- The resulting stack with a non-empty continuation/remaining list is the result of applying the stack to the first word of the continuation list and passing the tail of the list along.

Notice that id is actually doing word composition – it’s composing itself with the head of the continuation/remaining list.

With that done, here’s the implementation of the word composition struct:

template<typename... Words>
struct word {
  template<typename Stack>
  struct apply {
    template<typename... Remaining>
    struct continuation {
      using stack = typename id::apply<
        typename id::apply<Stack>::template continuation<Words...>::stack
      >::template continuation<Remaining...>::stack;
    };
  };
};

So what’s going on here? Well, id is used to set a starting stack value and then pass it through a list of words. The inner use of id is constructing a single word out of an inner list, and the outer use is composing it with the remaining outer list. It’s quite hard to describe in English!

Finally, here’s the eval metafunction:

template<typename Word, typename Stack = stack<>>
struct eval {
  using stack = typename id::apply<Stack>::template continuation<Word>::stack;
};

Again, id is used to set a starting stack value and then pass it through a word.

Primitives

With the evaluator done, let’s create a few primitive words so it can be tested out.

Here’s a primitive which pushes a type value onto the stack:

template<typename T>
struct push {
  template<typename Stack>
  struct apply {
    template<typename... Remaining>
    struct continuation {
      using stack = typename id::apply<
        typename Stack
        ::template push<T>
      >::template continuation<Remaining...>::stack;
    };
  };
};

Here are some integer primitives:

template<int I>
struct int_wrapper {
  static int const value = I;
};

struct add {
  template<typename Stack>
  struct apply {
    template<typename... Remaining>
    struct continuation {
      using stack = typename id::apply<
        typename stack_drop<Stack, 2>::stack
        ::template push<intc<
          stack_index<Stack, 0>::stack::value
          +
          stack_index<Stack, 1>::stack::value
        >>
      >::template continuation<Remaining...>::stack;
    };
  };
};

template<int N>
struct int_ : push<int_wrapper<N>> {};

And finally a primitive which swaps the top two values of the stack:

struct swap {
  template<typename Stack>
  struct apply {
    template<typename... Remaining>
    struct continuation {
      using stack = typename id::apply<
        typename stack_drop<Stack, 2>::stack
        ::template push<typename Stack::top>
        ::template push<typename stack_index<Stack, 1>::stack>
      >::template continuation<Remaining...>::stack;
    };
  };
};

Let’s test it out!

#include <iostream>

struct ten_and_five : word<int_<5>, int_<10>> {};
struct foo : word<ten_and_five, swap, int_<20>, add> {};

int main() {
  std::cout << eval<foo>::stack::top::value;
  foo x;
}

Improved Primitive Definitions

Once you have a sufficient number of primitives you can simply define other words using them instead of writing complex code involving apply and continuation. However, to get to that point involves lots of boilerplate.

To improve things, you can define metafunctions to automate this process. For example:

struct add  : func2_to_word<boost::mpl::add> {};
struct minus :func2_to_word<boost::mpl::minus> {};

I also recall using X-macros for more complicated words.

These will be left as excessive to the reader.

Interesting Things #1 – Word order

An interesting thing about stack languages is that you can easily factor out words without changing the program.

Here’s a modified version of the test program:

struct five : int_<5> {};
struct ten_and_five : word<five, int_<10>> {};
struct foo : word<ten_and_five, word<swap, word<int_<20>>>, word<word<add>>> {};

While the words are named differently their order is the same and thus the output is the same. This property will not hold if you do things with the “scoped continuation” as explaining below.

Interesting Things #2 – Quotations

Quotations are essentially a list of words which exist on the stack. They are analogous to first-class functions in traditional programming.

Two primitives which you will want for dealing with quotations are call and if_then_else, which you can learn about in the Factor manual.

Here’s how you could use them:

template<typename... Words>
struct quot : push<word<Words...>> {}

struct foo : word< quot<a, b>, call > {};

struct bar : word< quot<a>, quot<b>, bool_<true>, if_then_else > {};

Interesting Things #3 – Continuations/Remaining

Recall earlier I mentioned that implementing words using continuation/remaining lists is more powerful than the alternative. Well, part of the reason is because you can make use of that list when defining words. Program manipulation and introspection become possible!

For instance, our push word could use the head of the list as it’s argument:

struct foo : word<push2, bar> {};
// would be same as:
struct foo : word<push<bar>> {};

Or we could add (basic) if/then/else syntax:

struct foo : word<if, pred, then, quot<bar>, else, quot<qux>> {};
// else is optional
struct foo : word<if, pred, then, quot<bar>> {};
// pred is optional
struct foo : word<if, then, quot<bar>> {};

Or we could push that list onto the stack as a quotation which could be used to model exceptions or goto:

struct foo : word<word<push_rem, foo, bar>, call> {};

These are just a few examples – there are tons of different things you can do!

Full code

My original library code is a mess but here’s the code used in this post:
http://pastebin.com/vhDjGvFB

Posted in Programming | Tagged , , , | Leave a comment

Why don’t we take all the naming problems and push them somewhere else?

Naming class members can be a mess in C++.

The simplest idea is to name them like any identifier:

class foo {
  private:
    int size;
};

That’s nice, but what if we want to create a size member function? Unfortunately, you can’t have a a member with the same name as a member function, and so we’ll have to change things up:

class foo {
  public:
    int size(); // we could have also used get_size() and left the member alone
  private:
    int m_size;
};

This isn’t too bad (although I much prefer the first version), but it allows subtle bugs to arise (as seen here http://stackoverflow.com/questions/10678559/c-small-typo-causes-unspeakable-pain/10678689 )

class foo {
  public:
    foo(int size) : m_size(m_size) {}
    int size(); // we could have also used get_size() and left the member alone
  private:
    int m_size;
};

m_size isn’t being properly initialized in the constructor! Not a huge problem anymore as newer compilers should be able to catch this.

So, is there a solution to this silliness? Well, sort-of:


namespace actual_class {
  class foo {
    public:
      foo(int size) :size(size) {}
    protected:
      int size;
  };
}
struct foo : actual_class::foo {
  typedef actual_class::foo get;
  foo(int size) : actual_class::foo(size) {} // in C++11 use constructor inheritance instead
  int size() { return get::size; }
};

This takes advantage of derived classes shadowing their base classes. The possible constructor bug can be eliminated with shadowing, and you don’t have to add extra characters to get unique identifiers.

Is it a good solution? Well, it’s probably better to stick to m_, but it’s worthwhile to know.

Posted in Programming | Leave a comment

Scheme with C++

I’ve been looking around for a way to embed Scheme in C++ and so I’ve been doing some research. The following is what I’ve read from the docs and keep in mind I haven’t done much coding in them other than compiling some example programs.

First I looked at GNU Guile. I had high expectations, but the more I read about it the less interested I became. It’s just too bloated and too slow, not to mention that it has terrible support on Windows with the only option being Cygwin.

Next I looked at was Chibi Scheme which looked wonderful; small, simple, and portable. The only problem was that it was too lightweight and not fast enough. I’ll recommend using Chibi for lightweight scripting similar to Lua.

Moving on to compiled Schemes, I looked at Chicken, Gambit, and Bigloo. All three of these are interesting in that they compile to C code, which obviously implies easy interop with C/C++

Chicken, like Guile, was disappointing. It looked great for writing Scheme programs, but failed to deliver on embedding inside C, although it did have a nice FFI. I may be wrong on this, but I don’t believe Chicken has good support for Unicode, well at least not as good as the others. Also, it seemed to perform the worst on benchmarks of the 3 compiled Schemes.

Gambit on the other hand, looks great for embedding inside C++. In fact, it’s the only implementation that mentioned C++ in the documentation – the others were entirely C based. Windows is fully supported, although MSVC lacks some GCC optimizations and so MinGW seems to be the best choice. Unfortunately, it has two flaws: 1) it lacks native threads 2) the GC is stop-the-world. These are not huge problems as it supports green threads and the GC can be configured to block less, although these are not ideal solutions.

And finally, Bigloo which seems to solve Gambit’s problems: it uses incremental Boehm GC and it has support for native (POSIX) threads. Well, at least that’s how it appears – the docs are less clear than Gambit’s. Sadly, the FFI is much less nice than Gambit’s and Windows support isn’t stellar – it’s MinGW with some pthread emulation. Oh well, I’d rather play favorites with Linux.

Well, that’s it. I also looked at some other Lisps like Racket and CLisp which were too large, but otherwise good. 

In conclusion, Chibi for lightweight scripting, Gambit for the average embedding in C++, and Bigloo for when you need high performance real-time embedded Scheme. Oh, and Chicken otherwise, although honestly a full-blown Lisp makes it seem unnecessary.

 

 

Posted in Uncategorized | Tagged | Leave a comment

C++ Sucks

Disclaimer: This should be titled “Things about C++ that suck,” but “C++ sucks” is a much better search term.

1. Too many ways to write identical things.

This is a language smell. Ideally, there should be one way to write things, not multiple. For instance, there are at least 9 ways to create an alias to an unsigned long int:

typedef unsigned long int foo;
typedef unsigned long foo;
typedef long unsigned int foo;
unsigned long int typedef foo;
unsigned long typedef foo;
long unsigned int typedef foo;
using foo = unsigned long int;
using foo = unsigned long;
using foo = long unsigned int;

The fact that ‘typename’ and ‘class’ can be used in template declarations is rather silly, especially since ‘class’ is only enforced for template templates.

Having both ‘struct’ and ‘class’ is a waste of keywords. I prefer ‘struct’ as defaulting to public gets used much more often then defaulting to private.

Trigraphs are another issue. I can’t see any use for them anymore other than backwards compatibility.

2. Templates are an unholy mess.

Templates are great for their intended purpose: generic types. Attempting to do metaprogramming with them is torture.

The 3 most obvious things are ‘typename’, ‘template’, and ‘this’ used inside of templates. They’re not incredibly hard to use, rather they feel inconsistent with the rest of the language. Major compilers seem to do fine without them – perhaps I’m missing something but it really doesn’t seem necessarily to have them anymore.

Inconsistency is a real problem for templates. Specializations are a real issue here – some things you can, some things you can’t, and others you are severely restricted on. And why can’t parameters be evaluated in specializations?

Metafunctions and types aren’t very type safe. There’s no language feature for them, and so you’re left coming up with your own standards. Also, while tmp practically requires a recursive approach, doing so often causes compiler crashes as everything must be evaluated at compile time – even branches that cannot be reached.

3. The standard library is part of the language

What I mean by this is that many things cannot be done without using the standard library. Some language features even require it, the most notable being certain exceptions, ‘typeof’ and the new initializer lists.

The thing that really bothers me is that perhaps the most used container, std::vector, involves magic. The reason for this is that there’s no standard way to resize allocated memory. realloc() somewhat works, although it doesn’t work for non-pod data types. It blows my mind that the committee has been rejecting improvements to memory allocation for so many years. If 2 functions were added, realloc_nocopy and alloc_size, then I would be very very happy, as (somewhat) efficient memory allocation could finally be possible!

Well that’s all I’m going to write about. There are quite a few other sucky parts of C++, but those 3 are the ones that bother me the most.

Posted in Programming | Leave a comment