I've made some progress on my entry. For the first time I'm trying out Lua to write an entire game. It's been a blast putting my newly acquired javascript knowledge to work. That's right, JS made me a better Lua programmer. Though I'm starting to appreciate both languages a lot more, there's just something great about how they approach functions and data that open oh so many possibilities. Being able to generate and assign functions on the fly is invaluable, and I couldn't help but grin after writing the helper functions that generate the code for my primary event system and hook them up automatically.
TechnicalSo, the library I'm working with is Love2d. It comes with most things you need for a game, including a nice graphics api (gl based and very well suited for anything in 2d), input, sound, and even box2d physics if you need it. It's quite easy to jump into, though it's still up to you to supply the framework around it for a serious game. After an afternoon of toying around with Lua "classes", I was able to recreate my basic game framework that I normally write for SFML and the like. It's basically on off-screen render of a fixed screen size that is scaled to fit the viewport maintaining aspect ratio (I like my fixed resolutions that scale), plus a stack based state system (think GM rooms, but on a stack so when you add a menu it pauses the gamestate, and when removed you're back where you left off) that also supports running substates (rooms within rooms? Sometimes I barely understand it too but it's there).ProgressI have the basic framework hooked perfectly into Love2d's callbacks, and events trickle down (and also back up) as needed. I also have a rudimentary GameState with an entity system that manages game objects, plus a test object (player). Had to learn to draw the players in batches, while allowing different frames and all that (the same procedure should come in handy when I do tilesets). I started working on a grid based Level class.So that's not even the progress I'm excited about. A crucial part of my gameplay is gonna be pathfinding, so I started building it into my level class. Last night I implemented A*, which is actually a first for me. My previous attempts at A* always ended with me settling on something simpler. Well this time I didn't back down, and I'm proud to be able to move forward with a solid algorithm backing me up. It wasn't easy, and even after getting it working "in theory" I ran into a few silly bugs while dealing with the data (just typical), keeping me from laying eyes on the results just yet.But alas, the trouble has passed. So here's a screenshot of the pathfinding in action:
Quote:
Very nice aeron. I just wrote an A* implementation for the first time last week as well, it's well worth it :P
It's also useful for more than just pathfinding (AI decisions, for instance, and testing whether something is within a space or not). In that pic of yours, if you wanted the path to be taken more along the middle, you can 'weight' the tiles directly adjacent to the walls with a slightly higher movement cost.Ahhh Love2D/Lua sounds interesting, I'll have to mess around with that after I'm done messing around with a bunch of other stuff.
Ooooh, A*, my favorite programming problem! I need to finish my graphics engine so I can finish my 3d-destructable-terrain game so that I can make my RTS, cause I've got a wicked fast A* in Objective-C.
Just curious, are you using Manhattan distance (axis-aligned), Chebyshev distance (diagonal cost is 1), or modified Chebyshev (diagonal cost is sqrt(2))?You could modify your code such that on tie, the square with the lowest Euclidean/Chebyshev/modified-Chebyshev distance-to-goal is chosen. Basically, on a tie, figure out which square actually is closest to the goal, and use that. This ought to bias your paths to a diagonal zig-zag towards your goal, and since that value is only used for tie-breaking and not as an actual heuristic, it preserves optimality and other things.
Alternately, you can add that distance-to-goal tiebreaking value to your heuristic (multiplied by some small value, like .001, first). You lose a bit of optimality depending on that small value, but its negligible. Basically, what happens is you effectively over-estimate the distance to the goal, which leads to paths that /may/ be longer, by an amount directly correlating to how much you overestimate. For example, lets say your distance heuristic for a specific cell is 10 (10 moves away from the goal). To bias it, you have an epsilon of .05, and you find that your modifier distance-to-goal is also 10, because you are a straight line away from the goal. Thus, your heuristic for this cell is 10 * (.05 * 10), or 10.5.Now lets compare it with another situation. Rather than being 10 straight blocks away, you are 5 to the left, and 5 down. This means that your heuristic is still 10, and the modifier distance-to-goal is 5 (because chebyshev diagonal cost is 1). Thus, the total heuristic for the cell is 10 * (.05 * 5), or 10.25.The practical result is that the path prefers to angle towards the goal, even though it obeys the axis-aligned movement rule. A side effect is that the path no longer is guaranteed to be optimal, but it still is guaranteed to be optimal to within 1 + epsilon. If your epsilon is .05, it means paths can be 1.05 * the length of the most optimal path. A useful tradeoff.There are a few minor caveats with this technique, chiefly the sub-optimality that I mentioned, and also a more important one in which that this is absolutely useless if you use Euclidean-squared as your metric because of exponential growth - but one shouldn't use Euclidean-squared as a distance metric in A* anyhow.I would help with your pixel art, but this semester I'll barely have any time to work on my own projects, if any at all. But good luck finding one! Back in the day I would have said to go look for people in PixelJoint… but that was years ago. I wonder if they're still active..