imps should probably "compete" for tasks
Closed this issue · 5 comments
One thing is rather annoying with how imps take tasks, and results in very slow building of the dungeon: they do not "steal" a task from other imps which are far from the spot of the task. This can be mostly noticed when digging: the imp which just dug the wall go back at lair, while a far away imp will eventually come to claim the land.
Funny, just a little while ago I was thinking about this, too. I'm not sure yet how to program thus properly, but I definitely agree that the current job scheduling code is not very good.
I do not know how you design your AIs, but my own research for another foss game (to improve it) led me to the GOAP paradigm (inspired from STRIPS), which you can find documented in various places, but notably https://archive.org/details/GDC2006Orkin .
The website where it was hosted with a bunch of other useful links died recently, I think it can still be found on archive.org, but I lack the search skill on this place sadly.
The idea is, you implement a bunch of "actions", each of them have a bunch of pre-conditions and post-conditions named "atoms". Then you give bots "life goals" (ground being clean, walls being dug, etc) and describe them the world's situation.
This gives you a graph, on which you can run a path-finding algorithm (A*, dijkstra, whatever) starting from either the "life goal" or the world vision (depending on the algo, it can impact speed or efficiency, apparently) and the path gives the list of actions the bot will try to run.
For C, I have found the GPGOAP library, which have some foreseeable shortcomings but is good enough for my current needs, I do not know if it could be ported or imported in a java project, but it's rather simple to use. Apache licence.
A quick search on github gave me some java stuff too, but since I'm not a java dev, I can't talk about them much.
I think this could help you.
The way I see how the game runs, I think you might have a state machine mechanism and run A* toward the 1st non-picked goal, and make them run to lair if no goal was found, and they continue until their goal is reached.
From what I have seen in the recastDetour library (used in both proprietary and foss games) A* does not allow for easily interruptible path finding, and from my understanding only allows to find a single goal, but Dijkstra algo is different: since it searches for all paths, it can find goals on the way that could be faster to achieve, if important enough. I think (and this is not just for you, I'm thinking for my own needs as well here) that this can be used to "keep in mind" other reachable goals with an associated cost, and pick them when approximative cost to the "ideal goal" is too expensive compared to the other goals.
I want to make it clear that I'm still learning on the topic, but perhaps those thoughts can help you find an acceptable solution for imp_city as well (acceptable being a mix of code maintenance cost, interest to implement, hoped for improvements, etc. Only you can judge. I'm just sharing some random stuff here, in the hope it can widen your horizons while not widen it too much so that you delay more new releases :p).
Well, what I described was invented by F.E.A.R. devs, and is, AFAIK still used in AAA games, despite being rather widely documented. It's a dangerous thing to follow the rabbit though!
The reason it was invented though, is that it is much easier to maintain than alternatives, as when the planner's code is written, you no longer have to bother maintaining the links between actions manually. It simply scales well from a work point of view, and might even end up with games that are interesting to play even for their authors!
In v0.28, the idle imp which is closest to the job should get the job.