Weekly Update 12.11.2014

edited December 2014 in Weekly Updates
Edit: additionally the character poser is working in perspective as well, forgot to post that but it is in one of the twitch streams I think. Also, I thankfully have been relieved of jury duty - they told me it could take up to a week and I frankly don't have the time or money to cover such a period of absence, so they dismissed me from duty which is great news. Additionally, weekly updates will be every Wednesday, but may fall over to Thursday if I can't get the video out on time.

This week I did a pretty huge cleanup on the code (I deleted thousands of lines while retaining the same functionality and more). I also added in collision detection, a context menu (right click menu), and some functions for spawning/removing/editing entities - mostly for the purposes of quickly testing stuff but also useful for the eventual sandbox.

Making the collision work was not exactly trivial but it is a lot easier now that voxels are passed to the CPU and meshed. It looks at all the voxels within a given cell and determines (based on a given threshold) whether or not that cell is mostly solid, air, water, etc. More granular collisions can be done in screenspace, but this is necessary for offscreen or hidden collision testing. This coming week I will be working on camera movement (following an NPC or trackballing around it), in addition to registering collision and behaving accordingly (i.e. climbing stairs automatically if you collide with a step, etc). I will also try to work on managing movement and collision when other NPCs are present.

Also, if you enjoyed the classic Master of Magic, you might want to check out my friend Aaron's game Worlds of Magic. He is running for Indie Game of the Year (in the top 100 now), so throw him a vote if you are feeling generous:


Also, David Sahlin, who I have known for almost a decade (since I worked on Genesis) sent me his ideas for a mod for VQ, drawing inspiration from the likes of Pokemon, Spore, etc - I think it is a pretty interesting idea and I would love to see someone make a mod like this:



  • Very awesome! And I'm glad you managed to avoid that jury duty. I'm sure collision detection and AI pathfinding will make for something interesting for people to discuss. Do you have any pathfinding method in particular that you're planning to use?
  • Pathfinding is already using recursive backtracking with a few modifications that bring it closer to A* performance.
  • Any reason you aren't just using A* to begin with?
  • Mystify said:

    Any reason you aren't just using A* to begin with?

    A* has advantages and disadvantages in comparison to other algorithms (like RBT). Depending on the heuristics you use, A* can sometimes involve more comparisons, a more sparse memory layout (and hence more cache misses or alloc time), or other downfalls. In many cases, you do not need an optimal path, just an "ok" path - for example, an NPC wandering about town to eventually reach a destination. Also, RBT is very easy to implement (A* is not that hard, but harder). I might end up using both - RBT for passive pathfinding or exploration, A* for everything else.

  • edited December 2014
    For those who aren't up to speed on all this stuff (like me!), here's an explanation of recursive backtracking.

    My summary (it ignores some elements and constraints for legitimate pathfinding, but hey. It shows the idea):
    Basically, the relationships beween all of your potential options can be represented as a tree diagram. Starting with your current position, say you have some options: A, B, C, and so on. You then test each option to see if it's valid (that is, you can take a step in that direction and it helps you reach your goal). If it's not valid, then you move on and try a different option. As soon as you figure out that something works (option B, maybe), you say "okay, that's my first move. What're my options after that?"

    Starting from node B, let's say you have 3 options: B1, B2, B3. You repeat the same procedure (that's why it's called recursive backtracking -- you're doing the same operation again, just starting in a different place), find something that works, and so on. Rinse and repeat.

    Let's say you reach node B2 and none of the options after that work. Oh no, what do we do??? Return to the branches that stem from B and see if B3 is a valid option. If it is, look at moves that branch out from B3. If it isn't, return to the initial list (A, B, C) and keep looking for something valid. Start with the C branch, then the D branch, and so on.

    Like the Wikipedia page says, you can modify the algorithm to stop after one solution is found, after a certain amount of time, etc.

    For those who know what they're talking about, how'd I do?
  • edited December 2014
    @PreacherJayne‌ great explanation, also for an interactive diagram this really helped me understand:
    (scroll down for interactive diagram)

    RBT can be used for pathfinding as well as maze generation (in fact, I use it to generate maze like patterns in some of the streets). Same principles apply, but when you are generating a maze you just choose a random direction for the next node (in pathfinding, you use a heuristic like best direction towards goal).

    BTW, this guy (Jamis Buck) has great explanations of almost every maze algorithm, with interactive demos and code for each:
  • Thanks for the RBT links - those are cool. It looks like a depth-first search where your graph edges are all possible atomic path pieces.

    Deleting thousands of lines of code in a week is impressive.
  • @tyler‌ thanks! Yes, what I am always more astounded by is when I delete/refactor a bunch of code, compile, fix one or two compile errors, compile again, and it actually works without crashing. :) Always makes me a bit suspicious....

    Depth-first, breadth-first, and RBT are actually very similar in terms of implementation.

    The actual algorithm I use is the Growing Tree algorithm, shown here (configured to run like RBT but capable of mimicking Prim's algorithm as well):

  • edited December 2014
    I think the pathfinding is looking fine. It is not supposed to be perfect because it is voxels with funky edges. You can eventually add in collision objects to add blockyness so they aren't running into fences.

    I also added a few posts to several threads you should look at them as I think they may help with the project including a generalized approach to scalable networking.
  • @Switch33‌ thanks, I have checked out a few of these, thanks again for all the resources! 99 percent of this stuff I did not know about (other than common things like node.js (which I am a big fan of, btw)). :)
  • edited December 2014
    @gavanw I updated the post on networking (http://voxelquest.vanillaforums.com/discussion/29/source-code-distribution#latest) for readability and fixed a few discrepancies that I needed to look up. It is still a bit open ended in implementation but the structural parts for networking are designed out if you read into it a bit.
Sign In or Register to comment.