[GA experiment] "The Village"

Posted By: Puppeteer

[GA experiment] "The Village" - 12/11/07 22:17

Well, i just started working on a genetic algorithm experiment or whatever
There won't be any kind of fittness just die or to survive which is kind of real natural selection.

What i gonna do is to create a village with max. 400 villagers.
Each villager has an own job, an own way of living (when doing what), a hobby he likes the most, a familie (housemates or however you call it), gender (male female) and an individual look (hair, clothing).

I will not generate random genes (except for the look) at the beginning, so they are at first all the same fintie state machines.

Each villager has its own phenotypes and genotypes and some jobs or whatever are recessive or dominant ( http://en.wikipedia.org/wiki/Mendel ). Which is in my opinion a more realistic way of simulating people ^^

The GA will even include when he does what and at which point he is going to eat to prevent him from dying.

With the job the family gets money and so they can buy food for themselfes, then someone has to mkae the food ready to eat, so they can eat it
And it is nearly the same with water: They have to buy it and drink it ^^

One important thing is that they can't buy water if nothing is in the store, so the jobs will have an affect on the hole village.

So those are the states:
Play -> hobby
Work -> job
Sleep
pray (in church)
meet friends
eat
cook
drink
buy food
buy water
make love ( )

Jobs:
Watergetter
farmer
nothing
merchant
thief (rare)

Skills which affect the health
fun
thirst
hunger
sleep

Each bot will have its own personal assets in the genes so for someone they like it easier to fall in love with them

Now i just finished the 2D-world script to display everything an now i am working on th e pathfinding... I think i may post a demo of the pathfinding stuff tomorow so you can play a around with one npc

Now i am tired and want to sleep so here is a screenshot

and here a world bmap i used


Have fun
Omega

EDIT: Damn i forgot one thing, they can get better in their jobs by reading books, so they will earn more money
Posted By: Nems

Re: [GA experiment] "The Village" - 12/11/07 22:50

Looking forwards to your results, I dont recall anyone actually developing along these lines so it would be fantastic to see it done.
Posted By: achaziel

Re: [GA experiment] "The Village" - 12/11/07 22:51

omega, sei mir nich böse, aber wieviele projekte haste nebeneinander laufen??

jaja, ich weiss, ich bin selber nich besser. lol
Posted By: Damocles

Re: [GA experiment] "The Village" - 12/11/07 23:29

two suggestions:

make a fittnes function, based on the amount of "needs" beeing fulfilled.
For example:
no hunger/no thirst = 50%
having a falimily life = 20%
having a good job =20 %
having religious bonus (praying) = 10%

this way, the villagers will be selected at not just surviving by eating and drinking,
else there is not selection-pressure to do the other things.


Also you should not use a pathfinding (the village know how to reach the locations automatically)
Else the simulation will get quite slow, and thus the evolution is progressing quite slow.

The pathfinding could be developed by seperate genes is a seperate simulation.
Posted By: Straight_Heart

Re: [GA experiment] "The Village" - 12/12/07 01:03

@Damocles

Why should pathfinding be a seperate simulation? Its no different than the states he has already given the villigers beforehand, its part of the basic building blocks of viligers. So if you want to create an algorithim on the fly for pathfinding, you will end up with lots of dead viligers in the beginning, which make them not viligers but more simple bacteria. Since they are viligers I assume they are given these things beforehand.

I dont know if you should necisarily stay away from Pathfinding unless you can make it very efficient with a small amount of nodes/tiles.

I dont quite understand the whole GA reason to make a simulation like this. Everything is still predictable, if only just different colors and different attributes in later generations, unless my scope is nearsighted. If so could you explain what is possible for later generations?

Could natural born leaders emerge from the village? Could they learn to use weapons and train an army from young men? Could they work collectivly to research new technologies?
Posted By: Damocles

Re: [GA experiment] "The Village" - 12/12/07 01:14

I suppose the pathfinding is some kind of finding a way
from tile xy to another tile xy.
And the village having more than 10 tiles in x and y direction.

Evolving a pathfinding without any "precoding" of how
it should work will use huge amounts of "evolution-time"


The simulation would take forever to bring meaningful results
(especially if the fittnes function is just live or die)
-> the first hundret thousand of generations would simply die, trying
to find any meaningful path to move on.

"you will end up with lots of dead viligers in the beginning"
exaclty that. But how are you supposed to select the fittest then, if
everyone is making sonesense. Evolution needs not just mutation, but also selection.
But selection means that there is are at least two parts, a good and a less good (bad).
If everyone is bad, there is not much to select.


GA can do lots of things, but the simulation must allow
the GA to solve that in a reasonable time.

Evolution is a type of search algorythm, where selection is the heuristic (evaluating
the quality of the direction) and mutation is the progression-step in the search.

-> roughly translated to A* : the "selection" is the heuristic
determining if the next step is a lower eucledian distance than the previous,
and "mutation" is the step going to another node/tile.
A* can remember past moves, but evolution forgets them at each new step.
So you need at least a heuristic to keep a senseful direction.

Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/12/07 03:49

Quote:

two suggestions:

make a fittnes function, based on the amount of "needs" beeing fulfilled.
For example:
no hunger/no thirst = 50%
having a falimily life = 20%
having a good job =20 %
having religious bonus (praying) = 10%

this way, the villagers will be selected at not just surviving by eating and drinking,
else there is not selection-pressure to do the other things.



Maybe i should make a fittnes function but not exacly like that, because for example not everyone has to work (but can) some women may stay in the kitchen cooking and buying stuff so the men could work and earn money for the family which is some kind of team-tactic and so requires a fittnes function which awards such a behavior.

Quote:


The pathfinding could be developed by seperate genes is a seperate simulation.


I think this is not really necessary, because this is not about simulating most stuff via GA it is about trying if could use GAs to simulate individual lives of villagers in my "real" game and there i won't solve the pathfinding via GA too

@ achaziel:
Is ja für mein richtiges Projekt Abgesehen von dem arbeite ich halt noch für jemanden anders aber sonst wars das eigtl Nur arbeite ich halt atm an vielen Stellen meines Projekts...
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/12/07 03:53

Quote:


I dont quite understand the whole GA reason to make a simulation like this. Everything is still predictable, if only just different colors and different attributes in later generations, unless my scope is nearsighted. If so could you explain what is possible for later generations?

Could natural born leaders emerge from the village? Could they learn to use weapons and train an army from young men? Could they work collectivly to research new technologies?


No, they won't form an army to dominate our world The GA reason is simply not just making the villagers better, it is too about simulting individuals and not just "cloned" FSMs
Posted By: Straight_Heart

Re: [GA experiment] "The Village" - 12/12/07 04:17

arent they just cloned FSMs with just "copied then altered" variables from their parents?

The villigers do get better as you say. So the first generation men would for example be very bad at fishing, and as they make childeren and generations, the kids would be experts at fishing right? But they wont be able to make their own pastimes or recreations, since every activity is premade. Wouldnt just a simple copy and paste from Dad's hairline and add a random number be enough?

Im not just talking about your game so dont take offense, but I'm talking about these simulations altogether. Everything in the end is still predictable, and if its truly emergent, then it might crash the computer.
Posted By: mpdeveloper_B

Re: [GA experiment] "The Village" - 12/12/07 05:00

this seems to be made with rpg maker xp, and this could possibly be interesting
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/12/07 13:40

I youse just RPG2000 bmaps ^^
@ Straight_Heart:
They don't get better in their skills, they are just fintie state machines with the conditions to switch a state.
I think it isnt that easy to let evolve some way of wasting time...
But they will have different ways to waste it ^^
I don't want to copy dads hairline because it should be really some kind of "sexual" reproduction, jsut like in mendels rules
Posted By: Damocles

Re: [GA experiment] "The Village" - 12/12/07 14:06

wasting time (relaxing) should increase the fittness function
by an amount, that cant be simply compensated by other actions. This
way, it will end up in your final creatures. Else it is removed by selection.
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/12/07 14:48

Wasting time increases the fun value
Posted By: EpsiloN

Re: [GA experiment] "The Village" - 12/12/07 15:51

If you want to simulate something like that , with only Natural Selection , (IMHO) I'd suggest you add 'strength' , 'intellect' and other skills like those to the villagers. It'll make them 'fight' for better statistics , for their jobs , and will produce , for example , stronger or smarter children , depending on the parent and his job. (In a few words , it'll work like a GA , without the A )

As for pathfinding , I dont have time to read all the posts in here about it , but it shouldnt be ignored and it can be easely build to 'explore' diffrent paths , instead of knowing them all. There are a few articles on GameDev about this 'exploration' with a pre-build lists of paths (or dynamic).
Posted By: Inestical

Re: [GA experiment] "The Village" - 12/13/07 04:27

Those look nice.. but I can't help it.. Those tiles are in RPG-Maker XP style, and I actually reconize some of them.

You haven't done the tiles yourself ne~

it's cool though.
Posted By: bupaje

Re: [GA experiment] "The Village" - 12/13/07 06:56

I don't understand all of this but sounds like an good way to generate a population of more interesting npc's.

One more job type you might add is mutated or 'eccentric.' In real life there would always be a few individuals who don't fit the pattern. You can generate rare individuals who have one or more states outside of the norm -walks in random circles, spends too much/too little time making love,eating, being aggressive or whatever. Could have a very short life or could start a cult -who knows?
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/13/07 17:01

Got the pathfinding ready
Still needs some improvement because sometimes it don't finds the right way...
But anyway:
Take a look at the pathfinding and decide if i should use an astar with 8 or 4 directions (you can toogle both with 'p')

Click me

Quote:


You haven't done the tiles yourself ne~



Right, but i can't do them myself because i am not trhat good in painting

Quote:


One more job type you might add is mutated or 'eccentric.' In real life there would always be a few individuals who don't fit the pattern. You can generate rare individuals who have one or more states outside of the norm -walks in random circles, spends too much/too little time making love,eating, being aggressive or whatever. Could have a very short life or could start a cult -who knows?



Yes already planed that
For example the thief state is really rare
But all the other states (and maybe other things ) are surprises
I may add something like fighting later (Guards and thiefs or maybe two villages each other)
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/13/07 17:12

Damn forgot the poll -.-
Posted By: mk_1

Re: [GA experiment] "The Village" - 12/13/07 17:39

Difference in programming between 4/8 directions isn't much but it looks better. Of course it's also slower so make use of speed improvements like a fast sorting algorithm for the open list (in case you use A*), binary or fibonacci heap for example.
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/13/07 17:54

Quote:

Difference in programming between 4/8 directions isn't much but it looks better. Of course it's also slower so make use of speed improvements like a fast sorting algorithm for the open list (in case you use A*), binary or fibonacci heap for example.


No it is retty much the same...
Even though i just have to remove 4 lines of code
But some paths are looking better with 4 directions and other with 8...
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/14/07 12:50

Now i think the pathfinding is finished
Here a screenshot with 400 pathfinding guys

Posted By: Michael_Schwarz

Re: [GA experiment] "The Village" - 12/14/07 14:01

whats that white milk all over the picture?

I dont want to be rude... but it looks like... ermm... sperm.
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/14/07 14:04

Sorry i forgot to clean my screen before making a photograph of it


-No
Those are the RPG maker clouds and they are red because it is evening and the sun is orange
Posted By: Michael_Schwarz

Re: [GA experiment] "The Village" - 12/14/07 14:06

Quote:

Sorry i forgot to clean my screen before making a photograph of it


-No
Those are the RPG maker clouds and they are read because it is evening and the sun is orange



Since when can we "read" clouds - is that some new form of handreading, mindreading.... CLOUDreading?
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/14/07 14:17

Quote:



Since when can we "read" clouds - is that some new form of handreading, mindreading.... CLOUDreading?


Where did you read read
Posted By: Michael_Schwarz

Re: [GA experiment] "The Village" - 12/14/07 14:41

Quote:

Quote:



Since when can we "read" clouds - is that some new form of handreading, mindreading.... CLOUDreading?


Where did you read read



in the previous, unedited post (and it doesnt really help to uncheck the "mark as edited" flag)
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/14/07 15:21

It wasn't necessary to answer a rhetorical question ^^
Posted By: mpdeveloper_B

Re: [GA experiment] "The Village" - 12/14/07 15:43

Quote:

I youse just RPG2000 bmaps ^^




sweet, that's quite a feat with 3dgs, i take it you know how to use the bmap functions well
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/14/07 16:01

Principally it is really easy you just need maaaaaaany windows...
I even made a year ago a better one which really uses the rims of those bmaps and not just this quadratic style so the textures fit smoth in each other^^

BTW: Wow... am i that stupid?
I wrote youse -.- >.<
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/14/07 16:14

If you wnat to see the code of this 2D space take a look at this and see how it principally works ^^

It is kind of buggy and still needs some improvement because in some cases it takes the wrong tiles... But i won't improve it anymore because this was just a test a year ago...

Have fun with it

http://rapidshare.com/files/76535914/RPG_Omega.zip
Posted By: frazzle

Re: [GA experiment] "The Village" - 12/14/07 19:08

Thanks for posting the code Omega
The concept is nice, I hope you will be able to finish it

Cheers

Frazzle
Posted By: Germanunkol

Re: [GA experiment] "The Village" - 12/16/07 12:14

the clouds move weird on my pc.
also, paths should have a lower "cost" than grass/terrain...

Micha
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/16/07 18:17

Yes, I already thought about it...
I have now completly new clouds and have the look like genes ready and am now working on some states, but having currently some problems with pathfinding and the states but i think i can solve it very quickly
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/16/07 19:14

Solved it.. i was awfully stupid to forget to set the movementforce back to zero -.-


BTW: Maybe you will call me a stupid spammer and maybe thats true but this is important
I have 1337 Posts, i will never make a post again just to have leet posts
LEET LEET LEET LEET LEET LEET LEET LEET LEET LEET
Posted By: frazzle

Re: [GA experiment] "The Village" - 12/16/07 19:24

Actually, you didn't spam at all, it's your thread and you commented on a problem just to mention that you sloved it. This equals no spamming
What I did, that's spamming

Cheers

Frazzle
Posted By: LarryLaffer

Re: [GA experiment] "The Village" - 12/17/07 06:00

Quote:


Well, i just started working on a genetic algorithm experiment or whatever
There won't be any kind of fittness just die or to survive which is kind of real natural selection.




That is excellent! After I saw your minesweeping implementation and told you i might have a go myself at some point, you got me thinking at what i could possibly do other than minesweepers. At the end i decided on ant colonies, one red and one black. The ants will collect food that will get randomly created in a 3d terrain. If the queen of each colony is well fed it will breed faster, if the ants are well fed they will fight better(when encountered with an enemy ant (SimAnts anyone?). If ants starve for a long time, they die. Anyhow, the idea is the same, that the simulation itself will provide for the fitness function, and I'm amazed that you're actually going for it. I hope you the Best of luck!!


I think you should still start with a random population for more emergent behaviors. Just don't let their health drop very fast. At least not before they have the chance to make love at least once, even if there's no food/water available. And I guess you know that your people should be attracted to others with high health(by some degree), otherwise there'll be no evolution.

I saw in your demo that you're gonna make like lots of houses, and i guess some will go fetch items from the store, other will hunt etc.. So you're gonna need some ownership rules as well, so people don't cook stuff in other people's houses This may work beautiful, cause if you pull it of then houses near water sources will become watergetters and houses near stores will rely on buying for water instead, since you are using pathfinding for your simulation, and time wasted walking is time losing health.

I just wanna say, this may not be as easy as you think. But I hope you don't give up on it, cause i'll be watching closely, waiting for that first demo.. good luck again



Quote:


I dont quite understand the whole GA reason to make a simulation like this. Everything is still predictable, if only just different colors and different attributes in later generations, unless my scope is nearsighted. If so could you explain what is possible for later generations?

Could natural born leaders emerge from the village? Could they learn to use weapons and train an army from young men? Could they work collectivly to research new technologies?




He's working on a Decision Making method. If I(the bot) can choose between hunting or buying food or sleeping or eating at any given time, what would I do so me and my tribe survives in the long run? To guarantee that your citizens become as healthy as possible is an extremely hard task when you're dealing with collaborating behaviors, and GAs seems very appropriate to solve this.
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/17/07 12:45

Thank you!
Quote:


I think you should still start with a random population for more emergent behaviors.


Yes i think if i use good random ranges i will get good results, i will play a little with the values around, but at first i have to try to get the script working
Quote:


So you're gonna need some ownership rules as well, so people don't cook stuff in other people's houses


I already solved this problem because each bot 'gets' an own house and a 'family ID' (0-5) and using those IDs the states get the psoitions where to go.

I think i will add at each bot a little GA which develops the working skills a little bit, so their work will be more or less effective, but i first have to get it pincipally working ^^
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/17/07 18:02

Very good news
I testet the pathfinding etc. with a 400*400 tiles level and 400 villager!!!!!
And still get 20 FPS if i disable my rendering function i get 60FPS (FPS are locked to max 60)!!!!!!!!!!
So i will improve the function that there will be all the time such an high amount of FPS
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/18/07 03:48

Now i have 60 FPS all the time

EDIT:
Sleeping and eating finished...


EDIT2:
Again some pathfinding probs not directly with pathfinding but with a good implementation and additionally working on some effects
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/18/07 20:39

And again i was awefully stupid and forgot to exchange some old values by defines

Heres is a new demo with 400 villagers go sleeping... i think i have to improve the pathfinding a little bit because it slows the FPS extremely down if there is one per frame...

What do you think about the sleeping state and the effect if you press esc?
http://rapidshare.com/files/77498345/GAEX.zip

EDIT: would be nice if you tell me about ur framerate =)
Posted By: LarryLaffer

Re: [GA experiment] "The Village" - 12/19/07 12:53

It was usually on 60, but when everyone pathfinded it dropped down to 23 the most


But even 23fps is fine, but apparently the pathfinding does a hell of a lot of stuff in one frame, and the game becomes choppy. That means something is wrong, cause if you're using pure A*, you could be calculating paths in 1000x1000 grids and still not get any 'chopping'. In fact you could well be doing 10-20 simutaneous A*s in one frame and not have a frame-drop, cause you're not using any c-traces, just passable/not passable tiles. So check that out

I do like the overall feel and love the 2d graphics. I'd change that resolution though; look how cool the screenshot i posted looks, the people are cuter and the graphics don't look pixelated any more. Also, you'll be able to see much more of the overall village, which is what you'd want in a GA expiriment 800x600, maybe even 1024x768..

For the effect, i could care less

keep it up,
Aris
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/19/07 13:23

I just tested a resolution of 800*600 and i get just with the rendering a framerate of 28FPS maybe it is because every tile is an own panel...
If i only render the ground (the tiles) i get 48FPS which means they are slow too. I think at first i have to improve them.
So now i will try using windows instead of panels
I hope it will work better ^^
Posted By: LarryLaffer

Re: [GA experiment] "The Village" - 12/19/07 13:47

that sucks..

Here's an idea..

I guess you're using an editor to place those tiles and make maps right?

Index your tiles like this:

1=Grass
2=Pavement
3=mud
-1=fence
-2=flowers

etc..

negative tiles are impassable, to help with your A* later on

so when you copy paste tiles in the map using your editor, you're gonna use seperate panels like you do, but when you click DONE, your editor creates a .txt file like this:

Code:

1  1  1
2  2  2
1  1 -2    (a 3x3 tile map, consisting of a pavement and some flowers on the lower right)

Now.. of course you can use this data for a very fast A* pathfinder.. and in the actual game, you're gonna use this data to create a humongous new bitmap file on the fly, using the new bmap functions(bmap_create, pixel_to_bmap, etc..). Start by creating a blank bmap, then read the first digit from the .txt file (f.e 1), open the corresponding grass bmap and add it to the blank bmap you created. When you're done, you'll have a huge bitmap that will hopefully be nicer to the fps

it's not the only way, but i think that's how i'd do it. It's a grid game, so it's wise to have an underlying grid structure in memory, instead of relying to the tiles themselves
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/19/07 14:24

Got the windows working

@ Larry

I have done it an other way:
I have three layers:
Groundlayer
Middlelayer
Highlayer

each one has a size of 400*400 (map size)
the A* just looks in the middlelayer array and checks
if(Middlelayer[posx+posy*world_size_x]==0)

if this condition is true the bot can walk to this position
With this three arrays i can create different objects on different grounds.

I create the maps via functions and don't have an editor i just use a function like
create_house(pox,posy)

For rendering i have an array with the size view_tiles_row*view_rows
and copy every frame the right values in it.
Posted By: flits

Re: [GA experiment] "The Village" - 12/19/07 14:50

strange i get a error if i try to start it
main.exe werkt niet meer
i treid login ass admin didnt work
Posted By: Puppeteer

Re: [GA experiment] "The Village" - 12/19/07 15:02

weird... but whats an "ass admin"
maybe the direct x dll is missing....
Posted By: flits

Re: [GA experiment] "The Village" - 12/19/07 17:20

administaror on vista
i have that file i dont know why its no working
© 2024 lite-C Forums