Monster pathfinding

I once wrote an algorithm which enabled a computer character to find its way through a maze. I didn't really know what I was doing at the time, but I got the idea when I heard about some research into robots that work together to solve problems. I came up with the idea of a character that replicated itself throughout a maze until it found the exit, then sent a message back through all its clones to the origin point, and then highlighted the path. Not necessarily the best path, but a path nonetheless.

Then I heard about a bit of research which showed that if you put a blob of slime mould in a maze, it eventually grows into a shape that shows you the most efficient path through the maze. Here's a video which is in German, but looks quite cool:

I didn't know it, but I had stumbled upon something similar to the A* Pathfinding algorithm, which is a commonly used method for giving computer characters some form of artificial intelligence.

Think about a game where a monster is trying to get you. The monster might just walk towards you all the time, but what if there is a wall in between you and the creature? Should it just stop, or should it try to get around the obstacle to get at you? If so, which direction should it go? And what if it's not just a single obstacle, but the monster is trying to navigate a field of obstacles to get to you?

This sort of thing goes on all the time in games. Think about a game like Starcraft, where you click a point on a map to send troops, and they have to walk around rocks or lakes to get there. Pathfinding has to happen often, and it must happen quickly. It looks like the A* method is popular and powerful, but I don't think I can use it my Dudegame because my maps are not simple grid systems. They have obstacles all over the place, and not in regularly spaced intervals. I could rework the mapping system, and make all the obstacles fit to regular patterns, but I don't want to. I think for now I'll just use dumb monsters that either follow a preset path or just move blindly towards you. I don't think Zelda had clever monsters, and that seemed to work out OK.

8-way movement

Just a quickie:

Dude now has different animations for each direction of travel. This seems to work well in the new version of the program.

Little top-down adventure engine: Dudegame!

In the interests of sharing, here is something I made which was prompted by our Code Club at school. They asked if they could make a top-down RPG game in the style of Pokemon or Zelda, so I though I'd better look into how to do it. Doing so has helped me understand Sprites a lot more clearly, so I should be able to go back and make better progress with the fishing game I started earlier in the year (I was having trouble with animation slowing everything down, and I think I know what I was doing wrong now).

Dudegame is really just a set-up for a game engine, and allows you to create any number of "rooms" which represent the different screens of a Game-boy style game and navigate around them. I have tried to make it as flexible as possible, to allow for expansion and customisation wherever possible.

Each "room" is stored as an object, and contains a number of invisible "obstacles" which designated areas that the player cannot enter. By positioning these carefully over the prerendered backgrounds, I can give the illusion of a 3D environment, so you can walk in front of this house and the rocks, but not through them.

I have also implemented two kinds of "portal", which allow the player to move from one room to another. Standard portals are placed at the edges of the room, so the player can go to the next screen and reappear on the other side.
Special portals would be placed over the door in rooms like the example, so you can be whisked away to an interior room.

I have done some basic animation on the main character. He is called "Dude", which is a suitably mundane name. (Fun Fact: the character of Guybrush Threepwood in the Monkey Island games was so called because he was originally created in a graphics package that saved images as "brushes", and his graphic was called the "guy-brush")

Dude has some animation frames on his arms and legs, but only faces forwards. That's not a hard thing to change, so that may be the next update.

Next big addition has to be monsters. There will be a few different types: ones that move in a set path, ones that more randomly (avoiding obstacles) and ones that move towards the player. The last one is harder, as some sort of path-finding will be needed to avoid obstacles.

Then we need to add a weapon for Dude. Then interactive elements (signs, for example), then friendly interactive NPCs. And monster projectiles. And an inventory. And some sort of quest.

Or, as seems more likely, I'll get distracted by something shiny and forget about it.

Here's a link to all I have done though. Feel free to use it:

Dudegame source files

Object tracking in Python

Some more progress. Since last time, I have discovered that there are always at least 3 ways of doing anything graphical in Python.

In this case, I was looking for ways of analysing an image and looking for specific objects. I'm doing this based on colour, as it seems easiest. Python has a function called Pixelarray which will take an image and convert it into a 2D array of individual pixel colours. For example:

Pixel[0][0] = (255,0,0) would mean that the pixel on row 0 and column 0 (top left of the image) is coloured red (the three numbers in the brackets represent the amount of red,  green and blue in the colour)

This is fine when you are wanting to change the colour of an individual pixel, but it doesn't work quite as well if you are wanting to READ the colours. For that you need some extra tweaking.

My program here has a small calibration sequence which waits for you to press space and then grabs and remembers whatever colour appears under the blue cross at the top of the screen.
Then it switches to a black-and-white display which discards all colours except the target colour.

Then, it starts tracking the object by searching for solid blocks of the target colour. Due to the grainy nature of cheap video cameras (especially under poor light conditions), lots of speckling occurs which may include colours close to the target colour. My program tries to discard those speckles by focusing on blocks where at least 90% of the pixels are the target colour. It essentially scans the whole image quickly, then when it finds a potential block it starts counting how many neighbouring pixels match.

There are software libraries that do this sort of thing much more cleverly, but I don't understand them. This seems to work for now.

The robot arm lives!

I got around to finishing off the robot arm today, and played around with the software that comes with it. It's not terribly easy to use, as it's quite difficult working out which motors to operate in order to move it where you want it to go. Also, I'm not very happy about the accuracy of the thing. Telling it to move a particular motor for 1 second in one direction followed by 1 second in the opposite direction does not result in it being back at the starting position. There's no feedback, so it can't tell where it is. I'll have to allow for the inaccuracies when programming it, which is a bit annoying. I know it was only 40 quid, but still.

 

Meanwhile the vision experiments are going well. I'm quite impressed by the speed of Python's manipulation methods. I should be able to knock up some interesting Augmented Reality things too.

Finally making some progress with the vision thing

Well, after a lot of messing around I stumbled across a far better way of doing the computer vision element for my OXO project. Pygame (which is a set of Python add-ons designed to handle graphics better than standard Python) has a camera module which, while it's not designed to work with Windows cameras, can be tweaked to do what I want far more quickly than the Python Image Library I was using last night. Now I can grab and analyse video at a much higher frame-rate, as you can see in this video:

I always feel like somebody's watching me

A tough night of tinkering. I decided to play around with the vision part of my OXO project. Specifically, I wanted to see if I could get Python to grab an image from a webcam and analyse it for objects.

I started off by googling "Python grab webcam image", which led me to install OpenCV, a high-end computer vision package. To be honest, I wasted loads of time playing with this, unable to get it to work.I couldn't find a binary, so I had to try to compile my own from source files, which is something I have no real experience of doing. After several frustrating hours I gave up and tried a different tack.

Pythom has some built-in image analysis libraries called PIL, which does some of the work for you, and there's a third-party add-on called VideoCapture which will allow you access your PC's webcam.

A bit of fiddling around and I eventually managed to get a way of quickly analysing all the pixels in an image and identifiying the ones I'm interested in. Here, for example, is it finding similar skin colours in a snapshot of me:

So, with this in mind it should not be too hard to identify a nought or cross on a sheet of paper, especially if it's a different colour.

Now it's half past midnight, so I must go to bed.