If anyone asks me to code a basic physics engine ever I’m going to stab them. Repeatedly. Making the bouncy rocks was far far too much effort, and as such, I’m far far behind my very rough mental schedule.
I’d elected to stray away from HitBoxes and masks because of all the triangles going on, and because of this, the rocks physics and collisions are all done via maths. Pure, simple maths, and lots of the % operator. And it killed me. Seriously. It was so so buggy and very hard to debug.
The end effect is pretty sweet, but seriously not worth a fortnights worth of coding. Plus it’s put me off this project. Eurgh.
(the rock in the air is flying. Not hovering.)
Yes. This is all I’ve achieved in 2 weeks, most of which has been holiday.
However, in the latter part of today I managed to get a very flexible GUI system in place, which should speed up that side of development.
Oh, and the workers have bags that are 30 rocks large, which is why they’ll stop picking up rocks after a while.
I wanted to have a prototype done by the new year, but it looks like that’s not going to happen.
Right, onto the worker’s commands.
What went well:
Note to self: Don’t be ill over the LD48 weekend. It really hinders your progress.
Spent a few hours ironing out movement bugs with ramps. They work perfectly in even crazy situations like these.
Also, I’ll be participating in Ludum Dare this weekend I’m really looking forward to it, and I’ll be posting blog posts periodically throughout the competition with my progress.
In other news, I got my new computer set up how I want it, and it’s a beast. Specs for anyone who wants them:
- CPU: Intel Core i5-2500K 3.3GHz Quad-Core Processor
- CPU Cooler: Cooler Master Hyper 212 Plus
- Motherboard: Gigabyte GA-Z68A-D3-B3 ATX LGA1155 Motherboard
- Memory: Corsair Vengeance 4GB (2 x 2GB) DDR3-1600 Memory
- Hard Drive: Samsung Spinpoint F3 1TB 3.5” 7200RPM Internal Hard Drive
- Hard Drive: Crucial M4 64GB 2.5” Solid State Disk
- Video Card: MSI Radeon HD 6950 2GB Video Card
- Case: Corsair 500R ATX Mid Tower Case (white)
- Power Supply: XFX 550W ATX12V / EPS12V Power Supply
Seeing as Ubuntu 11.10 doesn’t play nice with my graphics card, I’ve moved to Windows 7. Which means….
I’ve been wanting to use FlashDevelop for a while, and it is SO much better than using gedit and Terminal. I love it so much
The control are a bit weird. I apologise for that.
For the terrain editor, the green ghost shows which part of the tile will be left when you click. Clicking again in the same part of the tile will clear it completely.
To move a worker, first clear any tool you’re using with ESC, then click on the worker, then click where you want him to move.
Diagonal tunnels have to be 2 high to be able to walk through.
Ramps allow you to walk past as well as up, and trapdoors allow you to walk across them as well as up.
Yes, it basically is just a movement engine at the moment… if you find any bugs, shout at me!
Look at the following example:
How many iterations of regular A* would it take to find the path between the purple square and where the mouse cursor is? (the end of the corridor). About 20. 20 times the pathfinding code will loop through, adding to arrays and checking all the tiles around to see if they’re walkable. Not very efficient, especially with all those straight lines.
That’s what first got me thinking about this. The game I was working on was going to have lots of corridors and straight paths, so I started thinking: what if, instead of having to go along those straight corridors one by one, you could skip right over them in one iteration?
That was great and all, but surely finding the start and end of the corridor would take more loops, and possibly waste more time than it saved? Seeing as the terrain in this game was dynamic as well (the user could remove and add tiles), I couldn’t store a pre-set list of nodes at the end of the corridors and use them for path finding.
But what if I could dynamically generate them? That, and the previous idea of long corridors being represented as a start and the end node, are the principles behind this pathfinding algorithm.
Have a look again at the example:
How many iterations did I say this would take in regular A*? 20? With this method – 4. Yup. 4. That’s 20% of the original iterations.
How it works in context
The example above has 5 ‘nodes’. These are where the purple square is, all the three corners, and where the mouse is. The nodes are shown in red on this diagram:
The basic idea is just normal A*, but instead of using every tile, just the ‘nodes’ are used. Each node knows where the nodes around it are, and if there’s a node above, below, to the left or to the right of it. That node is then used as the next tile in the algorithm, missing out all the tiles in the long line between the nodes.
Of course, I’m sure this isn’t a new idea. However, if I added to the path:
New nodes are automatically added. This dynamic node creation is the real driving force behind this algorithm.
However, there are some limitations to how much A* can be improved upon in certain situations. Take for example, a map with a large open space. Every tile in that space becomes a node, referencing all the tiles directly around it as the nearest node, and the speed becomes exactly the same as normal A*. However, when there are lots of long corridors involved, the speed is increased greatly.
There are 2 parts to the implementation – the node creation, and the node-based pathfinding. The node-based path finding, as I’ve said, is basically just A*, but using the nodes instead of every tile, so I won’t go into it in great detail.
The node creation, on the other hand, is what I want to talk about. Node updating only takes place every time a tile is changed, not every frame, and when it does, there’s only a small amount of work actually done.
Take this example:
If I was to click on the square where the mouse was to create a walkable tile above that last node, the following would happen:
- The tile would start looking in all 4 directions for a node. As the tiles above, to the left and to the right of it are all not-walkable, it would only look downwards. Because of this, the tile knows it is the end of a vertical corridor.
- It would find the node directly below it. This node thinks it is the end of a vertical corridor, but with the introduction of the tile above it, it now stops being a node.
- The tile then looks at the old node’s connected nodes, and connects itself to the node below it, at the corner.
- The tile then becomes a node, at the end of the corridor.
The end result looks like this:
Of course, this is only one of few cases that could possibly happen. In general, this is what happens:
- New Tile (A) is made walkable.
- A looks upwards for a node.
- If A finds a node (B), it first checks if B is now part of a corridor instead of the end of one.
- If it is, A updates the node at the other end of B’s corridor (C), and tells C that A is now the end of the corridor.
- If B is a corner or a junction, A tells B that it is now there, and a new corridor has been created.
- Repeat steps 3-5 for the other 3 directions.
If that doesn’t make sense, I apologise.
Below is a link to an implementation of the technique. Click to make tiles walkable, left and right to scroll, and space to move the purple square to where the cursor is. You can also press Ctrl to spawn “enemies” that will follow you.
Also, if you mouse over a node, the node it’s connected to will point towards it, so you can see the nodes.
So… New stuff! It’s not Adventuring, but it’s based on the same basic idea… ish.
I took most of today writing a pathfinding algorithm, and I’m very pleased with it. It works like a charm.
And it came from turning on a light. Literally.
…the game is all about light switches, so you know, it’s not really a big leap.
So, the October Challenge is starting soon (well, in October) and I’m hoping it’ll give me that spark I need to actually get another game finished.
Damn, I love my new phone.
I got some coding done today. And by some I mean about half an hour.
But hey, I got the guys hand to move with the mouse. …that’s something, right?