Pathfinding is some kind of foul sorcery I never understood.
Apparently, I'm getting a grasp of it. But yeah, it's certainly a hurdle. It's one of those things that is so clearly /computer-y/. Humans, with our super-processor brains, can do the whole path-finding thing in our sleep, but for computers, they've got to check every possible path, because there's no intuition or heuristics at play. All the more efficient path-finding methods just do the barest minimum to not check every possible path.
I wonder if there's any cases of brain damage or disease that causes people to lose their pathfinding capabilities. Just climbing over the check-outs to get to the milk in the shop.
A* isn't too difficult. The 250 lines are probably for the graphical overlay. You should be able to accomplish it in about 50 lines.
Yeah. I read through all the code and could probably cut it down to about 100 lines. It comes with some additional stuff that is Godot specific (adding exit code to units so they can clear themselves from the map without needing additional code) and includes several variations - there's pathing code for just pathing, for pathing around obstacles, and pathing around obstacles and units. Obviously, I'll only need one of those.
The way I heard it, in the search for a good pathfinder they tried Algorithm version 1 (A1), then Algorithm version 2 (A2), then they decided that they could prove A2 was the optimal of all possible A-type algorithms, so they renamed it "A*" as being "the best and entirety of all 'A's, of whatever version..." (though, by tweaking A*, you can even get a version of Dijkstra's algorithm, should you so wish[1]).
I love how dumb that is. It was actually the Dijkstra's algorithm that I was thinking of before. In the code there's both a Cantor and Szudzik algorithm, however Szudzik is what I'll be going with.
Here's a
write up on them both for those interested.
Okay.
Topic 1: A* Pathfinding, ContinuedI spent most of last night and a good portion of this morning pouring over Heartbeast's code and commenting it myself. I think I have a decent grasp of how the algorithms in this work, and what tweaks I can make.
It's pretty elegant, though the code is...how to say? It's very Python. There are a lot of functions which perform only one method - I would have just put them in the main function, but I will admit that this did help chunk it up and make it more digestible for me.
When the game starts, an AStar object is created and filled with all the points on the map. It also keeps track of a list of obstacle points and player position points. The pathing grid that is shown is actually not all of what was processed, but an updated one which ignores units and obstacles.
This is all taken from a "board" object, which is the tilemap. I will use this same method for making the map of this little game. I could probably achieve this with random map generation (using the walker algorithm from Sewer Kings, or learning to use cellular autonoma, but I don't particularly want to bloat this project any more than I already have.) There is also an issue with this algorithm - if you choose a point that is inaccessible, it will explore all options that /are/ accessible before figuring out that there is no path. This means if I make a giant XCOM-style map, and if there's any regions that are inaccessible, then the processing time would bloat incredibly when you clicked on those inaccessible places. This is mostly just a note for myself for later.
The walls are actually indexed by group. Godot allows you to add such a property to any node. This means I can use a variety of things for cover (trees, snowmen, and rocks) but process them all the same way when it comes to path-finding.
After establishing the grid, it's just a simple check for where you clicked, then drawing a line to that point. Heartbeast built in several expected functions. For instance, I can limit the distance (obviously would call from a character's move-speed):
Clicking past 6 tiles just paths to the 6th tile and then ends.
I can also keep track of the line, and move the character to that point.
Basically, this is all I'll need to make a tactics game. It will require some polish and customization, but I think I'm at the right point to move on. My comments on the code pushed it to about 300 lines of code. I should be able to cut large swaths of it, because there are a lot of redundant/unused functions and some that are specifically for different types of games.
Figuring out line of sight and shooting is going to be tough, because I won't be able to reuse this code to do it. But it should be possible to check if a straight line from the attacker to the target meets an obstacle. There might be some issue here because of unit differences. The grid is calculated based on the tilemap size (64x64 here).
Also a note on the resource-based saving. The Resource files, I mentioned, are written in plaintext and are loaded as plain text into the game. I'm fine with people finding them and setting their strength to 10,000 or something, but there is an issue when it comes to running executable code...You can get the OS to perform stuff by injecting code into the save and have Godot execute that upon load. I'll find a way to hash it and unhash it or something.
Author
Topic: Can delphonso make a commercial game? (Read 49528 times)