Qbasicnews.com
November 15, 2019, 10:20:56 AM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: [1]
  Print  
Author Topic: Another algorithm challenge  (Read 2832 times)
Agamemnus
x/ \z
*****
Posts: 3491



« on: February 21, 2006, 01:30:09 PM »

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...
Logged

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.
Ryan
Wandering Guru
***
Posts: 338



WWW
« Reply #1 on: February 21, 2006, 02:37:02 PM »

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?
Logged
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #2 on: February 22, 2006, 01:44:01 AM »

It's still in production.. It was announced in August, some screenshots were posted, and no news since then.

http://www.caesariv.com/
Logged

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.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!