Wednesday, March 21, 2012

n == 3

Progress on hallways continues to grind along, never as easy as it appeared in the distance, but always in motion.  I spent a while getting A* to filter out open squares and their neighbors, to prevent leaks; now it's developed a tendency to search forever without finding its destination.  I'll be ramping up the unit tests to get a handle on this business, most likely.

That said, it's starting to look reasonable for the case of just 3 rooms, if we can look past some minor door placement issues:

I redid the positioning in a new way that gets rid of the skew we had before; now it just scales the raw coordinates (which are too close together to begin with) by a constant factor, increasing that factor if things turn out to be too tight.  Nice and simple, but it doesn't solve the problem of A* searching forever.  Hallways must somehow be cutting off doorways, but it's a little difficult to get visibility into how unless I build a bunch of new (probably sorely needed) instrumentation to help me see.

I find myself pondering again an idea that had occurred to me before, which was to route hallways first and then overlay rooms on the intersections.  This would have some advantages, but brings issues of its own.  The more I think about it, though, I think it may be the way to go.  Guess I'll sleep on it.


  1. Hi Luke,

    It would be great if you could post some details about the software development methodology you're using to write this game. I think some of us could use the information.


  2. Methodology? Not much of it. Hack, test, hack some more. What would you like to know? Perhaps a more specific question? Do you want to know technical details, architecture, or what?

  3. Technical details sounds good

  4. On which aspect? I'm trying to get you to ask a question specific enough to actually answer. This blog exists in general to discuss technical details (among other things).

  5. Ok, let's say on the subject of testing. I am interested in how you do the testing part of the game for this A star search - how do you make sure that your implementation works ? I am not specific enough, because I don't know any tech detail about the game besides the fact that you're using Boost (and obviously C++)

  6. Sure, I recognize the difficulty of asking specific questions based just on these blog posts. Just trying to figure out what you're interested in.

    As I posted a few days back, I actually just recently started setting up automated testing for this project. Partly that's just been due to laziness and a desire to hack away without making it feel like work, but it also has to do with the somewhat experimental/exploratory nature of the work so far. I'm mostly trying to prove out basic concepts at this stage; it's not quite prototype time anymore, but I'm favoring immediacy so that I can explore ideas of what could work without worrying about ideal program structure. Given this, I don't mind if I'm accumulating some design debt that will necessitate rework later.

    Of course, the further I got without at least having a testing framework available to me, the more I began to regret it and suspect that the lack of testing was slowing me down. I'm finding the exercise useful, actually, in the sense that it's proving for me once again how much time you can throw down a hole created where a test should have been. That's why I bit the bullet and got started with Boost.Test recently.

    So far I haven't done any correctness testing on the A* search, but it's the next thing I'm going to do, to get past the current block. I anticipate a pretty straightforward approach -- just set up a bunch of level schematics with known room locations that are chosen for ease of reasoning, and assert that the correct paths are found.

    Depending on how much success I have with that, I may have to slow down a bit more and develop some instrumentation to help me visualize the search and see where it's going wrong. I want to do an overlay to show the graph on top of the level, for a start, and ideally I'd like to be able to step visually through the level construction. Accomplishing that could be a bit of a strain for the fairly primitive game loop code; currently it's done in the typical top-down fashion, something like:

    while (true)

    To see A* work step-by-step, I'd need to worm the UI refresh and input polling way down into the astar_visitor object's examine_vertex() function. Doable, but somewhat disruptive. However, I may be able to get enough of what I want with more modest measures; we'll see.

    Incidental to this notion of taking the time to instrument your code so you can see what's going on, I'd recommend this fantastic talk that I watched the other day:

    There are a couple of great tech demos right up front that I promise will make you want to sit down and watch the rest. The demos show development tools with a feedback loop so instantaneous, it has the potential to dramatically change the way one is able to work with the subject. Of course, the demo problems are somewhat cherry-picked for suitability, and he glosses over discussing the time investment in such tools (not really the point anyway for him, but relevant to me). Anyway, I think you'd enjoy it.

    Thanks for your question and ongoing interest in the project!

  7. The talk is amazing, thanks for sharing it!