I need some hints or pointers on how to implement a certain scheduling program. It's based for an RTS-like game where you have buildings and units. Buildings can train units, certain units can construct buildings. Some units/buildings requires certain buildings to be constucted before they are available. Certain units can also gather resources which is required ro train more units/buildings. My idea is to create a scheduling program to calculate the fastest (or at least very fast) way to reach a certain goal, a specific number of units/buildings/resources. I need some ideas on how to implement this, some efficient scheduling algorithm I could use. It's based on optimal conditions so I won't consider small uncertain details like the time it takes to units to walk between their assignments, that would prolly be too hard :).

I believe that is called planning.
Big area of research, unfortunatly, its mostly NP-complete.

Topological Sorting.

Maximum Flow Problem.

Couple options:

1) play the game alot, figure out the recipes and script them.
2) find some heuristical approach. Rather than planning the entire build order just plan the next thing to build based on board information: do i have enough money, do i need more units, do i need tanks, etc.

I'm sure there are more options. But #2 is a nice direction. You proabably don't want long term planning in an RTS because plans always change in reaction to what your opponent is doing. Having a long term plan and sticking to it is a perfect recipe for loss in RTS. The "what to build" question is more easily approached by:

1) what do i most need?2) are there dependencies I'm missing?     |     |--> if yes, build a dependency, end logic3) do i have enough money?     |     |--> if no, either build a resource building or end logic assuming you'll have more money next frame4) do i have an available builder?     |     |--> if no, either build a builder or end logic assuming a builder will become free shortly4) all pre-requisets are met so build my item.

-me

Palidine: I'm not exactly writing an AI (bummer posting this in the AI forum :) ), but a tool that generates the most efficient build order so people can use it instead of testing themselves. Of course it's only effective at the beginning of the game since there are so many factors later that affects (expansions, lost units, buildings etc...).

My first (naive?) approach would be representing everything as states and doing a breadth-first search, but that will consume quite some memory.

I did have some thoughts on topological sorting as mentioned, but given that the number of units/buildings are variable plus the resource income (which also depends on the number of workers) makes it a bit harder...

Quote: Original post by Magos
Palidine: I'm not exactly writing an AI (bummer posting this in the AI forum :) ), but a tool that generates the most efficient build order so people can use it instead of testing themselves. Of course it's only effective at the beginning of the game since there are so many factors later that affects (expansions, lost units, buildings etc...).

apologies for poor reading comprehension =)

Quote: Original post by Magos
(which also depends on the number of workers) makes it a bit harder...

Dunno if this helps but, most RTSes have a constraint that only one worker can unload at a time. Unloading takes a specific amount of time. This puts a cap on income rate per resource field.

-me

Quote: Original post by Magos
Palidine: I'm not exactly writing an AI (bummer posting this in the AI forum :) ), but a tool that generates the most efficient build order so people can use it instead of testing themselves. Of course it's only effective at the beginning of the game since there are so many factors later that affects (expansions, lost units, buildings etc...).

My first (naive?) approach would be representing everything as states and doing a breadth-first search, but that will consume quite some memory.

I think you'd actually do quite well with a simple method like this. I'd just generate all the potential successor states, and use a simple heuristic (eg. fewer buildings left to built = better) to order them, so that you're always expanding the best solution. Checking for equivalent states (eg. with the same buildings + units available) will help keep it short, and you can also consider dropping potential routes that are much worse than the best ones. Memory is cheap, and if you store things efficiently, it's even cheaper. :)

Quote:
and use a simple heuristic (eg. fewer buildings left to built = better) to order them

Since the idea of this program is to find the fastest possible build order I don't think that's a good heuristic, right? In Warcraft3 (which this tool is for) it's not neccessarily fastest to start making buildings right away.

My current implementation always expands the front node with the lowest time thus the first goal node will be the best one, however I'm facing horrible complexity problems even for simple testcases. I guess there's a reason no such program exists already :).