Sorting Algorithms(?)

Unity Engine
1

Hey all, I’m making a city-builder RTS and I could really use some help with the city builder part.

What I’m looking for is a way to assign the best mix of house-work for each citizen of the city.
The factors for the house is enough free room(for all family members), enough money to pay rent and highest “living condition”(nearby services and etc.)
For the job the factors are if work is available at said workplace, if the citizen is educated enough there, highest pay and highest “work quality” (perks, no pollution/dangers at work, etc.)
And both should be as close as possible.

This one got me real messed up, I’m starting to think this stuff is some college level sorting algorithm so I’m off to start reading about them.

I don’t want this as the main way of setting up the city(so i’m okay with a little heavy lifting here), during the game itself I’m planning on letting it change dynamically with the citizens moving around themselves, but I do want a way to set and initialize it to somewhat ideal conditions for quick testing and the map editor.

Hope I explained the problem well enough, any input from you guys(and gals)?

2

This sounds less like a sorting problem than a fitness algorithm problem.

You need to filter your citizens by various criteria and assign them to tasks based on their skills.

But before you can do this you need to clearly define the fitness criteria. And by “fitness” I mean “suitability to purpose.”

To help you think of the problem, think for instance how a bicycle and a car can both be forms of transport.

  • A car would be great for driving between cities.

  • A bicycle would be great for going to your buddy’s house one block away.

  • A car would be great to go pickup groceries

  • A bicycle would be great to go pick up a stick of gum at the convenience store.

Some elements that constitute each vehicle’s fitness are: cost and effort and speed and cargo capability.

At some point if you have to go 50 miles to pick up a stick of gum, the bicycle becomes inefficient time-wise.

If you’re only going 3 houses down the street, the car would be wasteful.

etc.

I think you want to come up with an expression that combines attributes of a citizen into some fitness score value for a particular task, then goes and assigns them. This is entirely a game design issue, and then afterwards you simply sort by that fitness score and choose the top one.

BTW, usually just using the default Array.Sort() call is adequate for 99% of all game design needs.

1 Like
3

Thanks for replying kurt, but I don’t understand how the car/bicycle example relates.
I understand how that works, a car has less cost per 1 unit of movement than a bicycle but a bigger upfront cost so a short distance has a lower overall cost on a bicycle.
I’ve used such things on pathfinding and action planning( which is basically pathfinding), but how would this translate to my current problem?

Maybe I haven’t explained properly, let me lay it out a bit more in a simplified version

If we have 3 classes, Citizen, House and Work

public class Citizen {

    public float education;
    public House house;
    public Work work;
}

public class House {

    public Vector2 pos;
    public float quality;
}

public class Work {

    public Vector2 pos;
    public float minEducation;
    public float quality;
}

I keep a collection for each of each of them for a faction.
I know the criteria you mention, but the only way I can think of applying them is by doing some ridiculous stack of loops and a ton of memory, I’m sure there’s a better way.

citizen has enough education for the work - citizen.education >= work.minEducation
shortest distance between house and work - in the game it’s the length of a path on a hex grid, but let’s just assume smallest (pos-pos)
and highest house and work quality available

the house and work quality and derived from other stuff not important, and there are some other factors I want to add, but I think if I understand how to combine these three criteria into a Array.Sort call i can just do it myself.

If I get 3 arrays, one for homeless/workless citizens, one for available houses and one for available workplaces, how would one go about assigning the values so all citizens have a house and work and are also… uhh… I’m not sure how to word this… as close to ideal as possible, or assigned with intelligence, so it’s not a “first come first serve” type of situation, if one citizen needs to take a “less ideal” house or job so another won’t be homeless this needs to take care of that, you know what I mean?

Sorry if I’m a bit all over the place with the explanation, thanks for your help!