Take all the time you need on developing a game. Live your life, do the things you do and enjoy! I don't think you should ever feel any sort of "pressure" to develop the thing you love, because you should love it first, and release it second.
We all underestimate how much work something will take, but for passion projects, tomorrow is another day. Success should be measured in what fun you had, haha.
Wonderful words of wisdom to live by for sure! Digging the hardware project-- I love mini consoles in all their myriad forms. Yours looks amazing and I will be following it with great interest. Maybe when it comes out I will make a tiny project for it!
---------------------------------------------------
As is tradition at this point, here is my long overdue annual 'I'm not dead yet post' since I struggle with regular updates.
Many life / job changes going on since last time, and a LOT of Starmush changes. Previously I discussed unexpected graphical issues I was encountering (tiles and some other components were not reliably drawing out of the blue despite no changes to those systems). This ended up pointing to a larger issue with incompatibility in the version of the engine I am working in, and led to me having to port the whole thing forward, bug hunt a bunch of odd things, and rewrite chunks of my systems that relied on some now deprecated functions.
One of these losses was unfortunately an undocumented behavior I was relying on for the time travel mechanic (because I am smart and that is definitely a good stable foundation to build a mechanic around lol. Lesson learned-- while things can just 'work' and that's good, at least release the dang project before the cumulative effects of software updates change the functions you work in jeez). This led to time travel being replaced with another mechanic that I found to be just as cool in execution but more useful, though it took a lot of brainstorming and testing. Details on this are forthcoming, but it is super exciting to me.
In the realm of lateral unit research / unit type swapping, things were progressing smoothly in a manner that I thought would be sustainable to get playtesting going within (albeit very late) until I found that some of the abilities were being held back by my primitive collision avoidance script. Like, REALLY being held back. Using some abilities while trying to get dwellers where they need to go was proving way too micro intensive because of their lack of pathfinding. I decided it was finally time to just buckle down and make a full grid-based navigational system for unit movement and interaction instead of relying on my simple steering script. Thankfully some assets exist for purchase in all engines for grid-related stuff, and I used one as a basis to start on, though I have had to radically customize it for all of my odd choices and mechanics, and add a lot of functionality it did not have to suit my needs. After much fiddling I have beautiful pathing and local collision avoidance working in tandem at last:
And lo! In the year of 2023 it came to pass that units don't get stuck around the simplest of corners anymore, and intelligently find their way as you direct them!Yea so it doesn't look that impressive but this radically changes the way a lot of stuff works on the back end, and makes it WAY more user friendly, both with basic orders and unit abilities. It does however make the resource-related systems a nightmare to troubleshoot, but that is a post for another time.
As a technical highlight, I want to go over something that seems simple in pathfinding systems, but is actually a bit of a hurdle. I think I found a novel solution to it and I want to share it in case it proves useful to folks.
THE PROBLEM:A* pathfinding systems are fantastic for finding paths around obstacles. This being stated, in its most basic form it does not do a good job getting you to where the next best guess is if there is no viable path. With multiple groups of units moving about simultaneously, other dynamic stuff like buildings being placed, spells and abilities flying around that mess with this etc., it becomes very difficult to figure out where you went wrong in your pathing, and therefore what on earth the 'next best thing' even can be defined as in your planning.
Instead of figuring out exactly where a path goes wrong, I figured that there must be a cost effective way of finding a guess that was 'good enough' for the purpose of trying to send a unit across a ton of terrain to a spot that might not be navigable, or for them trying to make a best guess when their original options are all exhausted in such a manner that they don't just stop what they are doing and give up completely.
THE SOLUTION:There are multiple ways of approaching this issue that far more competent developers have devised, but I didn't really find anything that I understood fully enough to devote time to. This being stated, while trawling through the Warcraft 2 source code for potential ideas (Patrick Wyatt's bytemask and length-based pathing is amazing and efficient but not something I am up for trying to replicate), I noticed the recurring use of Bresenham's Line Algorithm. After a bit of a Wikipedia dive on the subject, I found that this indirectly inspired an answer.
Bresenham's Line Algorithm is awesome. It is one of the very first computer graphic algorithms, developed in 1962 by Jack Elton Bresenham at IBM. In very simple terms, it can efficiently find a line between two points in the form of connected grid squares using very simple midpoint maths. This is obviously useful for drawing lines, but it is also useful for doing a bunch of other things if you have something that relies on grid-based calculations (like paths!).
My rough idea was as follows: It is inefficient to try to iterate backwards through the terrain from your goal with A* to try to find the nearest spot that is navigable. It is much more efficient if you could instead only check navigability when you know that you have crossed impassable sections of terrain, so instead of having a check per grid space you instead have a check per potential obstacle, which should be (in most cases) a small fraction of the CPU cost of checking the entire line. Illustration time:
This shows step by step what happens when I run my best guess script. Green is starting position, red is the end goal the player clicked on. Orange represents the different test points we are checking as they advance from both the start side and the end side. Blue filled in tiles are impassable. Further explanation below.I have a couple of iterations of Bresenham's running at the resolution of the navgrid (7x7px). It only checks the contents of each cell on the navgrid once. When it reaches a new cell, it simply looks up the data on the navgrid (i.e. 1=impassable, 0=clear). I have one script for each type of check I want for simplicity:
Bresenham_To (advances until it hits an impassable obstacle, and stores the position right before it)
Bresenham_Thru (advances through an impassable obstacle until it finds a free spot, then stores that position)
With these building blocks in place, let's find the best guess in the above image. Steps below correspond with the number on the given frame for reference. These steps are done in a while() loop where it simply alternates between which side it is checking from. The overall number of times it runs is limited by an arbitrary number of cycles (I use 10 at present) to make sure it doesn't go forever and it doesn't take up too much CPU agonizing over finding the bestest guess of them all.
FIND YOUR BEST GUESS:
--------------------------------------
1) Randomly choose if you want to begin checking from the start point or the end point. This one is beginning from the start point, shown as a green square. Move to the nearest obstacle, through it, and then until you hit the next one. Check if this test point is contiguous*** with your start point. If it is, check if its contiguous with your goal test point. If it is , your goal test point is your final position. As it most certainly is not in this case, move to step 2 (if it isn't contiguous with our start point, the last free spot before the obstacle was our best guess). (***I am using the word contiguous in these cases to mean that it is connected with the other spot by a path calculated with A*).
2) Check from the opposite side (in this case now the end point). Move to the nearest obstacle and through it. Check if this test point is contiguous with your starting point. It isn't in this case, so move to step 3.
3) Do the same process as 1 for the start side (minus the random choosing and the first move to the obstacle obviously).
4) Do the same process as 2 for the end side.
5) Do the same process as 1 for the start side-- AHHH. While we are now contiguous with our end test point (both test points are shown in red here), we are no longer contiguous with our start! This means the last point we found on our side is the best one!
6) Store the last known test point before the obstacle that was contiguous with the start.
7) Make a path to it, and that is probably as good a guess as my poor inadequately-coded unit can make.
--------------------------------------
There is a little bit more to it behind the scenes, like checking for edge cases where there may be a simple solution-- if there is only a single impassable obstacle between you and the goal, you don't have to run this whole process. This can be done by simply crossing the first obstacle from the start or end and using A* to check for a valid path. If you have one, then you know that your best guess is the last point in a line from the start direction before the given impassable obstacle. If this doesn't work, there is more complicated terrain in play.
Additionally, I had to write in some edge case checks to ensure that the scripts don't assume that diagonals are passable because it passes through them while completing its simplified checks.
I tested this in a lot of different configurations on paper and in-game and it seems to give damn good guesses even in bonkers terrain configurations (good in the sense that they look vaguely intelligent). That is a success in my book, especially given that we are using A* a number of times we can count on our fingers rather than a large iterative brute force nightmare.
NEXT STEPS:I have a bunch of bugs to squash and systems to finish filling out with the new grid stuff before it'll be in the realm of possibility to playtest sadly, so it will be another long while. I will make no promises and just see how I do in the coming year so as to not let anyone including myself down in my assumptions.
Now that things are coming together a little more smoothly, I have dedicated a little bit of time to sorting out a more fitting direction for promo art and theming that matches the new focus on abilities / spells. New promo art stuff is amorphous and not high priority at present, but something of interest is that I think the project now no longer fits its original title of STARMUSH. I did a lot of thinking on this based on recent changes to the game, and I have come to something much closer to the vibe I am shooting for that should play into the new art stuff:
MUTEMUS Pronounced Mew-teh-miss, (or moo-teh-moos for those who like its non-butchered Latin pronunciation).
More details and changes in this regard are coming. I am keeping the scope small and trying to just focus on the essentials for the game at present, so I will probably leave the title of this devlog as Starmush in the meantime until I get some new promo art going and have time to pretty the main post page up.
Community
