Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Another algorithm challenge
#1
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.

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...
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply


Messages In This Thread
Another algorithm challenge - by Agamemnus - 02-21-2006, 09:30 PM
Another algorithm challenge - by Ryan - 02-21-2006, 10:37 PM
Another algorithm challenge - by Agamemnus - 02-22-2006, 09:44 AM

Forum Jump:


Users browsing this thread: 1 Guest(s)