I'm an undergraduate who's researching random task or mission generation in open ended games. From what I have ascertained so far not many games have used this feature, and the few that have (Spider Man 2 uses it as filler in-between scripted missions) have not managed to make the missions very appealing, when compared to their scripted counter parts. For my main project I’m going to be producing a piece of software that will randomly generate missions. If I get it right the data that it produces could be used in any game, if I don’t get it right it’s a life of flipping burgers! So I’m looking for a little help, have any of you guy’s done any work in this field, or know anyone who has? Or if anyone is interested in doing any work in this field then let me know. Shaun

This is an interesting area to explore, but you're going to have to be more specific about the scope you're talking about. Are we talking rpg, RTS, or what?

Obviously the technique is probably rather cross-platform, but what is your research centering on?

There was an interesting post a while ago of generating fairly complex missions from the lay of the land, and having the players actions (or lack thereof) change the nature of it.

I can't remember the name of it, it was during the summer. Something about what would happen if you had a dragon and a village next to each other... Maybe someone else can remember.

The point of it was using the current state of teh environment to generate the quests. I think this is the coolest way, because then the player's actions create new situations that quests are designed from, instead of just spawning uber-boss in the same old dungeon.

This may be a 'duh' point. I'm not sure. Basically your first step, irregardless of which route you take, is to define what possible interactions the player can have with the world, as these are where your basic mission types will come from.

Adding complexity is a matter of designing a rather complex cause-effect relationship between the game and the player. This is where the bulk of your work will be in.

If you're working on making a demo, I'd stick with a simple rpg or some equally easy game to make (a reaaaaally simple rpg. read: map, character, monsters, NPCs, that's it) because this would provide you with the most actions with the least effort, since rpg's are designed to be abstract anyway.

I'd be interested helping you persue this further, if you'd like. I'm wanting to implement a random mission generator in my own game, and I'd like it to be complex enough that the player doesn't get board. It's always good to bang heads with someone.

This thread has some discussion you might find useful. I thought there was a more applicable thread somewhere, but I'm too lazy to find it.

I'll be working on a RPG that uses random quests, but it'll be a while as we plan to work on other games first in order to work up to the big one.

I didn't really ask anything specific, so I'll just try to describe my setup abit. Mine was made to work in a muliltplayer environment, and you want single player?

I have one almost finsihed up. I made it in a Nevermwinter Nights mini mmorpg server. The live DMs will run the real 'adventuring' quests, and my random ones were designed as everyday jobs.

Every type of npc can be approached and will generate a random task for the player based on their npc type (commoner, monk, shady character, guard etc...) When a player accepts one of these quests, they make up a new one for the next player that approaches them.

Also, the quests themselves can be finished in multiple ways. Saving a missing kid doesn't mean you have to return it to the worried mother, you can shove them down a well, sell them to science. etc.. [evil]

I had originally designed it as a very complex system, but in the end I dumbed it down to keep it simple for me the coder, and the players. It gets too complex with players logging in and out, and all these loose ends left everywhere.

Writing generic dialogue on it's own is really hard, but when you have to write generic dialogue with a bunch of unknowns, it's hell! After all the coding and setup, this always ends up being one of the toughest parts.

An example of how this all comes together and works. We have some monks in the temples of every town. They are neutral, and one of these reasons for being is to keep powerful artifacts out of the hands of good and evil to maintain the balance.

So, you talk to a monk. If his current quest is invalid (accepted by last player he talked to) He will quickly make up a random one, and speak his new text.

Something like, "We have gotten word that a powerful artifact has been spotted somewhere around (one of hundreds of random locations). Can you return it to us for (random prize)?"

If you accept, a random artifact looking item is created, and given some random powers, in that random place. You are given a key type item with the quest details, and when you get there, whatever is needed to happen, happens.

Once you get the item, what happens with it is up to you. You can return it to a monk, and get your agreed upon prize. You can return it and demand more reward. You can keep it (it is a powerful artifact, with some built in spell uses after all). etc...

Quote:

Original post by Vampyre_Dark So, you talk to a monk. If his current quest is invalid (accepted by last player he talked to) He will quickly make up a random one, and speak his new text. Something like, "We have gotten word that a powerful artifact has been spotted somewhere around (one of hundreds of random locations). Can you return it to us for (random prize)?" If you accept, a random artifact looking item is created, and given some random powers, in that random place. You are given a key type item with the quest details, and when you get there, whatever is needed to happen, happens. Once you get the item, what happens with it is up to you. You can return it to a monk, and get your agreed upon prize. You can return it and demand more reward. You can keep it (it is a powerful artifact, with some built in spell uses after all). etc...

This is what I'm talking about with the random spawn type quest. They're passable, but really boring, since their success or failure doesn't affect the game world at all.

Let me try to paraphrase from the post I was referring to earlier. It's been a while, so bear with me.

Let's say you have a world divided into zones. In each zone there is some controlling feature, be it a dragon, town, ogre nest, etc.

Each zone type has a compatibilty chart with other zone types.

Now, the player arrives in one of these randomly made towns and asks for a quest. The town is in the hills, so it's a mining town. Next zone over is a dragon lair. So one possible quest is having a dragon steal jewels (and the occassional villager) from the town. The village wants the player to go slay the dragon.

The player arrives at the dragon. The dragon tells him that the village is raping a mountain he's lived on for thousands of years. The player can either side with the dragon and go back and drive off/enslave/murder all the town people, slay the dragon or perhaps help negotiate some kind of peace accord.

If the dragon is gone, the zone is empty. The zone fills itself with something similar to one of the zones surrounding it. Maybe this means the twon expands into the old dragon lair, and begins mining it too.

Quests respawn like described above. Obviously depending on how the player responds, it will change the makeup of each zone, meaning that each game will evolve slightly different.

You may be saying to yourself "great, but how on earth do you code that." Obviously the best course of action is to limit the detail that the generic text that goes along with each mission tells the player. Players can see through computer generated clap trap anyway, so just have a small description of the quest.

An example would be something like "slay [monster] at [location]." Sounds dangerously close to a spawned mission, I know. But the point is that the world is changed permanently by the players actions.

As for coding the quest generation itself, this is slightly more complicated. When a player is in a zone, and gets a random quest, you'd check surrounding zones for incompatible inhabitants. (Town next to dragon in my example). The area tells the player to go get rid of the most incompatible inhabitant, or to go help the most compatible one.

Compatibility would be checked in some kind of adjacency table. After the player finishes a quest, the game checks to see if a zone needs respawning. If so, the zones surrounding it are chosen at random. A new zone of high compatibility with the chosen zone is placed in the vacant zone.

So this might mean that the empty dragon lair becomes home to a group of ogres, or maybe the town expands its mining operation, or maybe another dragon moves in!

Eventually you'll have a whole world that is rather compatible with itself. Perhaps this could be the end condition, or perhaps you'd randomly throw around some incompatible types just for the heck of it.

maybe some kind of hidden markov model, so that a chain of discrete Mission-Steps can be linked together to make up a more complicated story? Sorry it's so vague...I just remembered some code to randomly make up realistic sounding names using a similar strategy, so it prompted this thought.

Quote:

This is what I'm talking about with the random spawn type quest. They're passable, but really boring, since their success or failure doesn't affect the game world at all.

Our users have loved our setup. Ours are more complicated, as they are tied to a cool faction system, and the entire world is open to everyone of every level. All the monster come in 9 varieties, and our random encounter system makes suitable monster spawns for any group that is in the area. :)

Kind of hard to explain, but it's setup so that the player makes any character they want, then they can do whatever they want, and the world reacts to them by what they did. :) Instead of being forced to make one of a couple of set types of characters, and doing what the game wants you to do. There are no set npcs, everything is random. All the items are player made, with their own custom looks. The quest stuff is all tied up into a bigger system and it works really well.

I don't think random quests are all that good unless you build the entire game around that idea, instead of just having it as an extra feature. Every action the players do will make them friends and enmies, and affect who they can get quests from etc...

What about, semi-random quests. You design a pretty high number of posibilities in the first branch(imagine a tree like diagram), which are the type of quests the player can do.

For example, you put there killing quests, item giving quests, etc.

Second branch would be what are the posible items/enemies/objects the quest refer to.
The now I am not sure what you might want to put from the 3rd branch and so on. Those probably include number of objects and things like that. You might want to add more branches for things like time limit, and many other things you might want to do. The deeper the branches, the more specific the quests will be for each player, and the more branches you have, the more variate the quests will be.

That way you can design your world around the primary branches like Vampyre_Dark said.

Valiantly trying to have an opinion, I posted in the wrong thread. :)

check out
http://www.gamedev.net/community/forums/topic.asp?topic_id=278567
again.