Yeah, pretty much.

Ideally I would like them to figure out how seeds work on their own. Quite an AI feat, but possible.

More importantly, though, is that the NPCs end up constructing and maintaining an interesting city for a player to wander about in, without me having to program every alley, building, object and process in it.

How complex do the NPCs have to be to accomplish this? I don't know, and I'm hoping someone out there has an idea.

For a thought experiment, consider an NPC in a world that can simulate farming fairly realistically. There are plants, seeds, soil nutrients, sun, rain, seasons, and weeds. What needs to happen to make the NPC (and maybe his buddies) start farming?

I'm starting to think a pure brute force random evolution, genetic algorithms, would work best for this type of thing, as long as you get the laws of the universe correct.

Make the NPCs randomly do every action available to every object available to them in every sequence using every condition variable conceivable. Then see who dies. Don't do what dead NPC did again. Repeat until interesting.

Thoughts? Other approaches?

-Koobs

The general problem you are trying to solve boils down to a programatically generated system that is interesting for a person to explore. I've yet to see this succeed in any game I've played and I believe that this problem is equivalent to the unobtained holy grail of AI.

I wish to further comment because evolving cities and industry is an area I'm working on right now and I've been thinking about it for a while making slow progress.

First I would break up the overall problem into different wants and why you want them. For example:

growing city - interesting to see it evolve over time
people with needs and participating in industry - realistic and giving 'life' to a city
production of goods - desired to have a market economy with supply/demand and fluctuating prices
...

Now each one of these can be a very detailed issue to investigate and the reason for having them may or may not be aligned with the _goal_ of your game.

In my case, I want a game that has an interesting economy with supply/demand and prices because my game is a trading game. With that problem in mind, as I approached the problem of city simulations, I realized that having workers with professions, realistic building construction, and other such facets of a proper city were out of scope of the overall goal of my game. What really I needed was to have the supply/demand and market price of commodities. Then I could have systems that affect those values but those systems did not have to be realistic!

Anyway my two cents. Very interesting topic but it's overly broad and perhaps the answer lies within the realm of philosophy rather than engineering. :)

Sorry about my earlier post, I thought you were talking more about pure generation of all objects + world (no defining). What you have explain will require a lot of defining of objects, actions and rules. Otherwise the NPCs will have no idea what's going on.

One approach I've been thinking about is:

The system that is the mind of a NPC is setup like a state machine.
The external input to the system would be everything that the NPC can "see" and "feel". That is, objects within line-of-sight, weather, colours, materials, physics (gravitation etc), ongoing actions,.. Everything that is of interest for the decision-making.
From all this data, the system, containing loads and loads of rules (are we under water or not? are we standing? are we sitting? are we upsidedown? are we looking at santa claus? are we hungry? etc etc), would then generate a result which would be one of many predefined actions (walk, sit, go left, go right, cuddle, play banjo..).
Also, either the NPC would have to be able to identify objects as useful in different way (based upon their 3d-representation), or (easier) the objects would have to have internal rules that describes how they are allowed to be used.

As you can imagine there are a number of complications and difficulties with this approach, for example the matter of defining *good* rules and actions.

Doing this using a static state machine would, given the exact same external input multiple times in a row, always generate the same result.. And that's not how people work. If we fall off a cliff and break a leg, and find outselves in the exact same situation right afterwards, we don't wanna go down that road again.

That's why instead of using a static state machine, it would be better to use a dynamic one (aka. non-deterministic, NFA). Being non-deterministic it would basically allow for the state machine to modify itself (it's behaviour) upon runtime. If we fall off a cliff, we punish the system by modifying its behaviour.


It's quite overwhelming when you think about taking this approach for a fully enhanced 3d-environment, with physics and weather simulation and what-not. But if you start on a small scale, with simple NPCs and primitive actions/rules, I think it might be useful.


You also might find these interesting, it's about AI:
http://www.ai-junkie.com/ann/evolved/nnt1.html
http://www.ai-junkie.com/ga/intro/gat1.html

Quote:Original post by Koobs
For a thought experiment, consider an NPC in a world that can simulate farming fairly realistically. There are plants, seeds, soil nutrients, sun, rain, seasons, and weeds. What needs to happen to make the NPC (and maybe his buddies) start farming?

If you create a finite list of things to do, i.e. plant seeds, water seeds, harvest crops etc, then it would seem that it wouldn't be too hard to get an AI to solve. Maybe a genetic algorithm where the fitness is how many dollars worth of crops the farmer can bring to market at the end of the season.

But to have them come up with creative, unimagined products? Now that would be darn hard.

Maybe you could apply evolution/genetic algorithms to any problem you didn't know the answer to or wanted to see solved through evolution, but the problem is that the search space is too big (the amount of possible combinations) and you'll end up waiting ages for anything interesting to happen... But depending on how you define the variables that are to be mutated and evolved, the search space might be small. For example, if the two variables involved in the evolution are the action to be performed and the object(s) involved that can be associated with that action, then it actually would progress very quickly. For example, if some possible combinations involved in this sort of evolution are:

"Plant seeds" where "plant" is the action and "seeds" is a related object.

Or "planet seeds in black dirt" where "black dirt" is a further associated object.

So using this model you could define a set of actions and their related objects, and the evolutionary algorithm would go through all the possible combinations to find the ones that produced good results. But you already know the answers to these, so that would be kind of a waste of time to program... i.e., you know that seeds planted in water or grassy areas are less likely to produce crops than seeds planted in black dirt...

But how would you determine the fitness of an NPC's actions? If one NPC is the smart one that figures out that planting seeds will create crops which will benefit it, the other NPC's can just as easily eat the crops that that one NPC planted, deriving happiness from it, and therefore you would not be able to correctly grade the fitness of the NPC's (if you used the 'happiness' of the NPC as the criteria for fitness).

Quote:But how would you determine the fitness of an NPC's actions? If one NPC is the smart one that figures out that planting seeds will create crops which will benefit it, the other NPC's can just as easily eat the crops that that one NPC planted, deriving happiness from it, and therefore you would not be able to correctly grade the fitness of the NPC's (if you used the 'happiness' of the NPC as the criteria for fitness).

One way you could try it could be to not, define the items, so you just keep them as a bunch of variables, and perhaps a number as classification. Then you see what items come out at the end, and what they might match up to in the real world.

Also you might need more than one set of happiness for each individual. So that planting a crop and eating from it makes them happy, but if others eat from that crop it makes them even happier.

Calabi: I think I see what you mean. If I understand, you mean to generalize the characteristics of a thing with one or more numerical identifiers (or equivalent), which can be mixed, instead of simulating the object in extreme detail? I think that would be good.

trasseltass: I agree a dynamic system is a must if the NPC AI approach is taken, which I think I may.

As far as fitness functions go, survival I think would be a good starter, with others thought up later to keep things spiralling towards big cities.

The generalisation of the physical details seems to me to be the key to keeping the AI manageable. Even with genetic algorithms and gobs of computing power, any detailed interaction will take an extremely long time.

Would it be possible to bootstrap this process? I tried to elaborate on the idea, and botched about five paragraphs of examples. So I'll just say this: can the simulation start detailed, figure out a detail (series of actions, cause and effect, ect.), and make a generalisation assigned to one identifier for all NPCs to use in their figuring? Say, seed-placed-into-dirt = 'plant' and as soon as that is determined, others can just say 'plant' without having to re-simulate placing the seed into dirt? Would that be useful? How about possible?

Perhaps dividing intent and action could be another way to reign in complexity. So have the NPC think "I want that seed to be in dirt" and figure out seperately how that is accomplished. That way, planting:the-action and planting:the-intent could be evolved seperately and reused independently.

I'm beginning to think I should've posted this in the AI forum. Oh well, everyone likes AI, right?

-Koobs

I was thinking about something similar recently. One thought was that I don't really care if it's an NPC AI that's the cause of a crop being planted, I just simply want the crop planted once a game year. The planting of the crop may have certain requirements, quantity of seeds available and quantity of workers available are two that leap to mind (weather might be another). I would test to see if enough seeds and workers were available in the region and if there were then I'd allocate both of these two "resources" to a crop planting task. Graphicly, I could show this just by having workers randomly run around in an area. If a PC goes to talk to the worker he responds, "I'm busy planting crops" or some such thing. One or more added animations of seeds beig dropped adds to the illusion as would further pathfinding from a seed source to the seeds destination in the dirt. But in the end when the crop is growing, I'd probably still just display it as a 30ft by 30ft (or whatever) are of uniformly growing wheat.

That the resources exist, are available, and that the task begins on time would have the desired impact on the economy that i'd be looking for. If one of these elements are missing or something happens to the crop or workers, the supply of food is diminished and the price would go up for what is available.

I've been playing a game called dwarf fortress lately, and It has the kind of needs system you describe. Each dwarf has needs and wants. They need water, food, etc. Thier wants are things like a room(instead of sleeping outside or in the barracks). They also have arbitrary desires, like obsidian, cats or bracelets. If they get too unhappy, they go beserk. I guess you could make it so that if they are unhappy for long, they develop psychotic tendancies, instead of jsut going beserk. Crime will make your city interesting.

Friends tend to like the same things, so if you add friendships in there, that can be another inspiration to artisthood or insanity(lack of friends -> psychotic -> interesting, if its not real)So friendship's primary purpose(gamewise) is to Reinforce each other's wants. A person has an arbitrary desire for friends, Like "I want four friends" and if they have more than that, they weaken a friendship. Friendships are struck up arbitrarily when people meet. Some people will not get along for arbitrary reasons(diceroll)I suppose you could get really elaborate, like each person having a like factor for each of thier friends, with friendships sometimes breaking off, or aforementioned psychosis occouring if "nobody likes me"

People's desires and needs are tracked, and when a high desire is noticed, a corporation is created for that desire. Corporations hire citizens, providing them with money to buy what they need and want. Corporations will build buildings in order to fulfill production trees. Thusly: build a mine, an oil rig, a steelworks, and a munfacturing plant. Increase demand for power, and suck some off the powergrid. Ship oil to the manufacturing plant and steelworks(shipping demand), ore to the steelworks, and Build toasters at the plant. Make it a dedicated toaster plant, to discourage one corporation form becoming OMNI corp. each step increases the demand, but Building that step also increases the supply. Maybe Someone already had a steelworks, so only if the availability of a resource is below a threshold do you build your own. Maybe toasters also require plastic from a plastics lab, which uses oil. Maybe the oild needs to be refined.

Make up sound rules, then make up ai to take advantage of those rules. Change the ai or the rules as neccessary to build a good world. For example: manufacturing plant is pretty general, but you want lots of different corporations, so force diversity: make plants specific: a toaster plant. It coasts money to retool to make a different item, and the AI is adverse to doing this, but If demand/supply for that item is low enough to justify the cost of retooling, do it.

Corporations... will do all the world building. They will build housing according to demand, they will build skyscrapers on the city grid if they have enough surpluss cash. THey will employ people, etc. Some corporations will be criminal, and these will have different rules, but I feel the same motivations and general decision making algorithms. Corporations are created by the gameworld in response to demand. they hir emanagers. Did I mention that npcs should have skills that make them prefer and perform better in certain jobs?

The semi random desire->friends->corporations progression is an interesting take on the problem. In fact, I hadn't considered linking wants and friendships before, or even friendship's role in city building. That opens up some very neat possibilities for the NPC AI and should add a whole other dimension to the detail of the city, as well as providing a good mechanism to arrange the infrastructure.

How would the NPCs know how to make toasters, though? That seems to be a very hard question to answer, especially if they don't know what toast is. If you have some thoughts on how that might evolve from a toastless state, I would love to hear it. Once we figure that out, the system would take on a life of its own.

Also, a little side annoucement for anyone interested. I have started seriously thinking about specifics of how to implement this and I intend to write a library. Let me know if you would be interested in said library.

Keep the ideas coming!

-Koobs