Allow enemy creatures to move around

[crankycyclops]

Allow enemy creatures to move around in pursuit of players. Could implement a shortest path algorithm to determine which direction to take from current room, then allow it to choose that direction with some percentage determined by how "smart" the creatures is defined to be.

Creatures might also be able to pickup objects (especially objects like weapons, shields, etc.)

Not sure if I would want a creature to move each time the player enters a command or if I would want there to be a thread running in the background that moves the creature every x seconds. Having timed events in the game might make it more interesting (in fact, will put in another ticket for this!)

[crankycyclops]

A BFS search that locates the shortest path to the player will quickly get unwieldy memory-wise. HOWEVER, we COULD do a limited BFS search that says "if player is within a certain depth, do BFS. Otherwise, don't. This wouldn't consume too much memory.

By the way, I did implement a timer. So, there would be a timed event for the creature that would execute every n ticks (each tick is 1 second). Creatures could either move randomly, move toward the player via the shortest path (see above) or, most likely, some combination of the two (more likely to take shortest path if more of the intelligence attribute, etc.)

[crankycyclops]

Here's a question/solution I got from Facebook:

Me: Got a question for anyone who's done work in AI (especially AI in games.) Assume that I have a map with various "rooms" connected via north, south, east, west, up, down, etc. It's an unweighted graph. I want to give enemy creatures the ability to move around, and if they're within a certain distance from a player or other creature that they would want to attack, I want them to find the shortest path to the player in order to determine which room they should go into next, and then, according to the intelligence of the creature, pick either that room or some other random room given a probability. The intelligence of a creature will be configurable. Dumber creatures will pick the right next room less frequently than smarter creatures, which I hope will have the effect of smarter creatures being able to find players and other creatures more quickly. The only thing I'm trying to figure out is the shortest path. There are known algorithms I can use, but there are various space vs. time complexities that I have to consider. BFS is fast, but if I have a large map the amount of memory required will go up astronomically very quickly. I'm considering just doing a search down to a configurable depth. In fact, I might make some creatures more perceptive than other creatures, so that they can "sense" players and other creatures at various depths. If anyone has any recommendations, warnings, tips, etc., please feel free to share. Thanks!

Mark: you can assign monster prowess to some field that represents the amount of distance they can see in manhattan distance. Like if the player is 2 rooms south and 3 rooms west of an enemy then an enemy with a perception of 5 is aware of the player. Since you know the manhattan distance you can also use that to make the move outright, the monster moving west since it's the lower of the two distances.

Me: Thanks Mark, that was helpful. I didn't quite get that last part about the lower of the two distances, though.

Mark: the monster has the option of going north, south, west, or east. We know by the manhattan distance that there's a player to the south west, so we choose one of those directions, we choose the lower of the two, south(i misspoke) to move

Will probably use something close to this.

[crankycyclops]

Phase 1 will be to simply let any Creature wander at random. Phase 2 will be to select and implement a smarter AI algorithm for following the player around.

[crankycyclops]

Phase 1 will be implemented in #42.

[crankycyclops]

commit d15bd8a41968c9e0fabbdba2a5ade2d259582b73: added parser support for Creature wandering and added sample wandering settings to casper in game.xml

[crankycyclops]

Phase 1 is done. Phase two will involve investigating how Creatures might stalk other creatures, etc. Putting this on the backlog for now until I decide to continue work on it.