Full Version: Another algorithm challenge
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Challenge: Find a way to solve the following problem. It does not have to be optimal but it must be decently efficient. It should run as quickly as possible. Your solution can be a suggestion or a subset of the problem.


* There are n housing buildings and m worker buildings.
* Each housing building holds from a_max to a_min people.
* Each worker building requires from b_max to b_min people.

* All buildings are on an X by Y tiles grid.
* Each housing or worker building occupies a non overlapping portion of the grid of random sizes of x and y dimensions from a minimum of 1 to a maximum of 4.
* Each housing or worker building has a random set of "door openings" from which a worker or occupant can enter the building. The door openings are all tiles on the outside of the building. The minimum amount of door openings is 1, and the maximum is tiles all around the building.

* Each tile in the grid has a tile walking cost, from 1 to 5 and -1. -1 means that the unit cannot walk there.
* A worker going from a housing to a working building (or the other way around) incurs the walking cost of each tile. This quantity can be referred to as his "travel cost".

** The object.. as you may have guessed.. is to minimize the travel cost of N workers, by setting which workers will be assigned to which housing buildings. (Where they work is considered as given) Each worker should also have a travel route. (Workers can go through each other)

This can be further complicated by:
* Setting randomized ranges to a standard normal distribution centered on the mean with a standard deviation of half the mean.
* Giving weights to certain unique buildings that correspondingly reduce the travel cost of their occupants/workers versus other workers.
* Setting a "gradual optimization"/speed tradeoff variable.

This unspeakably difficult problem is inspired from a little conversation on unit pathfinding in the Caesar 4 forums. I know it is a lot to tackle at once so again, baby steps....

You can also talk about Caesar 4 here to keep this going...
So you're trying to get us to write your next big break out game for you? :wink:

I think I might like to give this a try, or at least start to. I can't imagine I'll get very far. I've always loved the Caesar games and didn't even see there was a 4th. Is it out or still in the works?
It's still in production.. It was announced in August, some screenshots were posted, and no news since then.