today I want to hear your opinion on the following topic :
What Level of KI would you feel satisfactory for your playing style ?
That means, for example, would you mind, if they stand all day long in the same spot ? Would you prefer NPCs to be talkative, wise-cracking wisdom spreaders or simple Quest- and Trade-O-matics ? Should NPCs be able to farm, repair their houses and use their equipment ?
So here are my thoughts on this topic :
1. Pathfinding.
As long as villagers move, they need to be able to find their way. I think everyone will agree that they should behave more clever than pigs, cows etc. which always end up at the lowest reachable point given enough time.
Also, to find a way you need to know where you want to go, which needs an aim in the first place, but I will cover that later.
The main problem I see with pathfinding is the fact, that Minecraft is a 3D-game like no other before.
Think about it : Every other game (as far as I know) is 3D but nearly never features multi-stories like minecraft does. If you are at bedrock level, there can easily be more than 5 stories of caves, randomly connected to each other or not, but all in the same game realm. Other games are in comparison only "2D", you have small overhangs, stories of buildings and stuff, but all those are more or less plain, in easy computable 90° degree angles. Caves or underground areas are often own realms.
Since I guess there will always be a possibility for NPCs to land in holes, ravines etc., they need a proper way to get back.
I see two possibilities for that : 1. They are "all knowing" which means they know the complete layout of the world. In that case you end up with with (probably) very high numbers of vertices (lots of caves intersecting, leading to high number of possible ways). More than 15 vertices produce insane amounts of possibilities, which are very hard / impossible to compute. 2. They remember, meaning they can trace back their own footsteps. Well, obviously that would need a memory for each individual NPC, which will get a lot very fast due to size of worlds and number of villagers.
Both variants still have a pretty obvious drawback : It only works until our wandering NPC faces a wall higher than one block. That means, with the ability to move they necessarily need the ability to place blocks themselves, if they are supposed to be able to come back to their home.
2. Aims
Like said before, every path needs an aim. Also, NPCs walking around aimlessly is simply a sad thing to look at ( at least I feel so). But what could be the aims of the villagers ? And most important, how advanced would you like them to be ?
My first guess would be to find shelter in their homes when it is getting dark. Also they could generally try to avoid darkness.
My second thought on this was the question, if they should be able to use the wheat farms, since I guess it is an obvious thing to do. They have wheat farms and we (players) get hungry. So they could get hungry and eat, too ( no, I'm not jealous :laugh.gif: )
Since this requires a hunger system and an individual inventory, farming routines and stuff, NPCs would produce even more load.
And now what about damage to their homes ? As long as they are able to move, it would look pretty silly when they just sat in their damaged homes at night. To counter this, they would need to be able to gather appropriate ressources and use them to repair their village. That could produce problems itself, since biomes aren't balanced to keep Villagers alive, meaning the next tree to farm could be very well across the next ocean...
Of course there is a lot more possibilities with that, but I wanted to keep the length sane :smile.gif:
3. Communication
.... I will post my thoughts on this tomorrow, it got faaar too late for me here and I stopped being capable to reread my own post for mistakes ( yawn :laugh.gif: )
I still would appreciate your comments on these topics very much. Kudos in advance to anyone who refrains to write tl;dr :wink.gif:
How in the world is this even the first "real" 3D game? If you want to ignore the thousands of 3D titles since 1990, I guess. And pathfinding implies theres a path the NPC's/mobs are even trying to reach. The only pathfinding minecraft has, is when either an enemy wants to reach you, or if an animal/mob's random direction choice is blocked.
I've never seen animals "eventually" end up at the lowest blocks possible. I've more often seen them at the highest blocks possible.
None of what you suggest makes any sense for minecraft either. I suppose next you'll be wanting a realistic impact system, limb damage, or smart AI that can avoid blows, run away when injured, or sneak up on the player? None of these things make any sense for Minecraft. Its like saying theres a problem with basic math skills for a 7 year old when they're not being taught integrals and matrices.
I would like Testificate "farmers" to not trample their own crops. That is all.
Edit: I don't think the problem is comparable to the Travelling Salesman problem at all. Mobs don't have a goal, the salesman does. If the goals of an NPC are rated on a simple priority list, this excludes the requirement for multi-goal processing, as the NPC would simply need to calculate the path for the single most important goal on their list. It then becomes a problem of
Determining the priorities of various tasks.
Determining how a goal is accomplished.
Determining a path to the goal.
Determining whether or not a goal has been accomplished.
Alternatively, it could become a Travelling Saleman problem if you took into account the effort required to do things.
However, the problem with mining to repair structures is how to determine if a block is being used for something else, and where it should gather resources from. If an NPC needs a block of stone to repair a house, how do you stop it walking over to its neighbour's house and punching a block off that? What if a player's house is nearby? They'd almost be working like Endermen, and with all the complaints they get.
It would be great to see some smarter AI. I think the villagers should:
-Get food when hungry (go to farm)
-Not destroy the farms
-Crowd into the church every 7 days
-Randomly decide to visit the other buildings once in a while
-Spend most of their time in their houses
-Repair minor structural damage (no building in TNT craters)
-Use an (infinitely filled) vault building to dispense repair materials instead of mining
-Walk on roads when possible
From a programming standpoint if the houses are organized as a set of points connected by roads then the villagers can easily find their way from one building to the next using simple recursion to decide which path to take. The priorities should go:
1. Eat
2. If Sunday go worship Notch for creating them
OR
Do job (loiter in job area)
3. If dark go home
Else
Go somewhere other than home to chill for a while
4. Go home and stay home until next day
There I did all the pseudo-code for notch's villagers =P
I would really hope to see reasonable pathfinding. Your concerns about minecraft's "3D" nature effecting pathfinding are unfounded.
<TechnicalRambling>
Minecraft is almost a best case scenario for a limited depth A* optimization. Dependign on implementation of the navigation mesh, the branching factor is always less than either 5 or 9. I would use the branching factor <5 implementation and get natural looking movement by making the target within the adjacent block the edge point closest to the centroid of the next 2 blocks in the path. If you add weights for edges that are asymmetric (can't be crossed form both directions) or previously traversed, use a distance heuristic that favors nearness in the y axis, and set your search depth to around 8 with a 2 block update frequency you will probably get pathfindign at least as good as most players after they run out of pickaxes.
Of course any implementation that ignores diagonal squares will produce less than optimal paths, but the reduced branching factor could make a tremendous difference for performance. As with any pathfinding problem, such considerations should be parameterized and tested during implementation. Also I am assuming the villagers wouldn't jump or break blocks. Jumping would increase the branching factor and breaking blocks would just make the entire problem far more complicated.
Aesthetic improvements to pathfinding such as favoring roads could easily be built into the weights of the A* implementation with negligible impacts on performance. However, specifying what a road is could be a bit memory intensive.
</TechnicalRambling>
Also, if a pit in middle of a village resulted in all the NPCs falling to their death it would be really pathetic.
Thank you very much for your feedback, especially to TrabberShir :smile.gif:
I'm sure I didn't get it completely though, why is the branching factor always smaller than 5 or 9 ? Also, non-jumping NPCs still would have a tendency to stay in holes forever...
@ TheAvatarOfWar :
How in the world is this even the first "real" 3D game?
In terms of world layout not display, my raging Padawan
I've never seen animals "eventually" end up at the lowest blocks possible. I've more often seen them at the highest blocks possible.
Are you even playing 1.8.1 or higher ? Or longer than some hours? Somehow I doubt that.
None of what you suggest makes any sense for minecraft either. I suppose next you'll be wanting a realistic impact system, limb damage, or smart AI that can avoid blows, run away when injured, or sneak up on the player? None of these things make any sense for Minecraft. Its like saying theres a problem with basic math skills for a 7 year old when they're not being taught integrals and matrices.
Learn the difference between suggestion and discussion. I didn't suggest anything for the game, I asked for your opinion and gave some thought provoking impulses to discuss about. You solely discussed about my impulses instead the question which I asked.
Your whole post was a very nice example why sarcasm based on false assumptions looks really, really dumb.
T'is my second post on this site, so please pardon any shortfall of my post, but I would like to know how does a testificate know what a house is and how do they know when to spawn?
Perhaps I should ask the question from the other direction. What qualifies as a villager house, and what are the prerequisites for a villager to spawn? A bed, chest, workbench, other?
T'is my second post on this site, so please pardon any shortfall of my post, but I would like to know how does a testificate know what a house is and how do they know when to spawn?
Perhaps I should ask the question from the other direction. What qualifies as a villager house, and what are the prerequisites for a villager to spawn? A bed, chest, workbench, other?
A house is solely determined by whether or not it has a "registered door" the doors are actually the "houses" so a house with multiple doors actually counts as multiple houses, all the other blocks just help a bit. See here...
Villagers breed whenever they are below the limit cap for that village. Each door is only worth .350 villagers so 3 doors means that 1.05 villagers are allowed, six doors means 2.10 villagers, nine doors means 3.15 villagers, etc.. Most villages spawn with more villagers than this formula allows during chunk generation which is why you never see any baby villagers or villagers with heart symbols (breeding) unless the village population has taken a serious hit or you have added more registered doors (houses) to the village yourself.
today I want to hear your opinion on the following topic :
What Level of KI would you feel satisfactory for your playing style ?
That means, for example, would you mind, if they stand all day long in the same spot ? Would you prefer NPCs to be talkative, wise-cracking wisdom spreaders or simple Quest- and Trade-O-matics ? Should NPCs be able to farm, repair their houses and use their equipment ?
So here are my thoughts on this topic :
1. Pathfinding.
As long as villagers move, they need to be able to find their way. I think everyone will agree that they should behave more clever than pigs, cows etc. which always end up at the lowest reachable point given enough time.
Also, to find a way you need to know where you want to go, which needs an aim in the first place, but I will cover that later.
The main problem I see with pathfinding is the fact, that Minecraft is a 3D-game like no other before.
Think about it : Every other game (as far as I know) is 3D but nearly never features multi-stories like minecraft does. If you are at bedrock level, there can easily be more than 5 stories of caves, randomly connected to each other or not, but all in the same game realm. Other games are in comparison only "2D", you have small overhangs, stories of buildings and stuff, but all those are more or less plain, in easy computable 90° degree angles. Caves or underground areas are often own realms.
The problem at hand is comparable ( I think )to the "Travelling Salesman problem ( http://en.wikipedia.org/wiki/Travelling_salesman_problem ), which asks for the shortest way between lots of travelling stations.
Since I guess there will always be a possibility for NPCs to land in holes, ravines etc., they need a proper way to get back.
I see two possibilities for that :
1. They are "all knowing" which means they know the complete layout of the world. In that case you end up with with (probably) very high numbers of vertices (lots of caves intersecting, leading to high number of possible ways). More than 15 vertices produce insane amounts of possibilities, which are very hard / impossible to compute.
2. They remember, meaning they can trace back their own footsteps. Well, obviously that would need a memory for each individual NPC, which will get a lot very fast due to size of worlds and number of villagers.
Both variants still have a pretty obvious drawback : It only works until our wandering NPC faces a wall higher than one block. That means, with the ability to move they necessarily need the ability to place blocks themselves, if they are supposed to be able to come back to their home.
2. Aims
Like said before, every path needs an aim. Also, NPCs walking around aimlessly is simply a sad thing to look at ( at least I feel so). But what could be the aims of the villagers ? And most important, how advanced would you like them to be ?
My first guess would be to find shelter in their homes when it is getting dark. Also they could generally try to avoid darkness.
My second thought on this was the question, if they should be able to use the wheat farms, since I guess it is an obvious thing to do. They have wheat farms and we (players) get hungry. So they could get hungry and eat, too ( no, I'm not jealous :laugh.gif: )
Since this requires a hunger system and an individual inventory, farming routines and stuff, NPCs would produce even more load.
And now what about damage to their homes ? As long as they are able to move, it would look pretty silly when they just sat in their damaged homes at night. To counter this, they would need to be able to gather appropriate ressources and use them to repair their village. That could produce problems itself, since biomes aren't balanced to keep Villagers alive, meaning the next tree to farm could be very well across the next ocean...
Of course there is a lot more possibilities with that, but I wanted to keep the length sane :smile.gif:
3. Communication
.... I will post my thoughts on this tomorrow, it got faaar too late for me here and I stopped being capable to reread my own post for mistakes ( yawn :laugh.gif: )
I still would appreciate your comments on these topics very much. Kudos in advance to anyone who refrains to write tl;dr :wink.gif:
I've never seen animals "eventually" end up at the lowest blocks possible. I've more often seen them at the highest blocks possible.
None of what you suggest makes any sense for minecraft either. I suppose next you'll be wanting a realistic impact system, limb damage, or smart AI that can avoid blows, run away when injured, or sneak up on the player? None of these things make any sense for Minecraft. Its like saying theres a problem with basic math skills for a 7 year old when they're not being taught integrals and matrices.
BBCode Render failed due to reaching MaxNestingDepth(80) for Tag: spoiler
My Signature Is Better Then Yours, Don't Hate
Edit: I don't think the problem is comparable to the Travelling Salesman problem at all. Mobs don't have a goal, the salesman does. If the goals of an NPC are rated on a simple priority list, this excludes the requirement for multi-goal processing, as the NPC would simply need to calculate the path for the single most important goal on their list. It then becomes a problem of
Alternatively, it could become a Travelling Saleman problem if you took into account the effort required to do things.
However, the problem with mining to repair structures is how to determine if a block is being used for something else, and where it should gather resources from. If an NPC needs a block of stone to repair a house, how do you stop it walking over to its neighbour's house and punching a block off that? What if a player's house is nearby? They'd almost be working like Endermen, and with all the complaints they get.
-Get food when hungry (go to farm)
-Not destroy the farms
-Crowd into the church every 7 days
-Randomly decide to visit the other buildings once in a while
-Spend most of their time in their houses
-Repair minor structural damage (no building in TNT craters)
-Use an (infinitely filled) vault building to dispense repair materials instead of mining
-Walk on roads when possible
From a programming standpoint if the houses are organized as a set of points connected by roads then the villagers can easily find their way from one building to the next using simple recursion to decide which path to take. The priorities should go:
1. Eat
2. If Sunday go worship Notch for creating them
OR
Do job (loiter in job area)
3. If dark go home
Else
Go somewhere other than home to chill for a while
4. Go home and stay home until next day
There I did all the pseudo-code for notch's villagers =P
<TechnicalRambling>
Minecraft is almost a best case scenario for a limited depth A* optimization. Dependign on implementation of the navigation mesh, the branching factor is always less than either 5 or 9. I would use the branching factor <5 implementation and get natural looking movement by making the target within the adjacent block the edge point closest to the centroid of the next 2 blocks in the path. If you add weights for edges that are asymmetric (can't be crossed form both directions) or previously traversed, use a distance heuristic that favors nearness in the y axis, and set your search depth to around 8 with a 2 block update frequency you will probably get pathfindign at least as good as most players after they run out of pickaxes.
Of course any implementation that ignores diagonal squares will produce less than optimal paths, but the reduced branching factor could make a tremendous difference for performance. As with any pathfinding problem, such considerations should be parameterized and tested during implementation. Also I am assuming the villagers wouldn't jump or break blocks. Jumping would increase the branching factor and breaking blocks would just make the entire problem far more complicated.
Aesthetic improvements to pathfinding such as favoring roads could easily be built into the weights of the A* implementation with negligible impacts on performance. However, specifying what a road is could be a bit memory intensive.
</TechnicalRambling>
Also, if a pit in middle of a village resulted in all the NPCs falling to their death it would be really pathetic.
I'm sure I didn't get it completely though, why is the branching factor always smaller than 5 or 9 ? Also, non-jumping NPCs still would have a tendency to stay in holes forever...
@ TheAvatarOfWar :
In terms of world layout not display, my raging Padawan
Are you even playing 1.8.1 or higher ? Or longer than some hours? Somehow I doubt that.
Learn the difference between suggestion and discussion. I didn't suggest anything for the game, I asked for your opinion and gave some thought provoking impulses to discuss about. You solely discussed about my impulses instead the question which I asked.
Your whole post was a very nice example why sarcasm based on false assumptions looks really, really dumb.
Perhaps I should ask the question from the other direction. What qualifies as a villager house, and what are the prerequisites for a villager to spawn? A bed, chest, workbench, other?
A house is solely determined by whether or not it has a "registered door" the doors are actually the "houses" so a house with multiple doors actually counts as multiple houses, all the other blocks just help a bit. See here...
http://www.minecraft...llage_mechanics
...and here, for more complete info...
http://www.minecraft...so-brief-guide/
Villagers breed whenever they are below the limit cap for that village. Each door is only worth .350 villagers so 3 doors means that 1.05 villagers are allowed, six doors means 2.10 villagers, nine doors means 3.15 villagers, etc.. Most villages spawn with more villagers than this formula allows during chunk generation which is why you never see any baby villagers or villagers with heart symbols (breeding) unless the village population has taken a serious hit or you have added more registered doors (houses) to the village yourself.