Hi guys, for a school project I had to make a character (I made an alien) and make it walk among a path. The creation went ok and making an armature (and rigging it) as well, but now I need to use weight painting to prevent deformation while moving the limbs (for the walking). I saw all kind of tutorials on how to do this, but when I open weight paint mode on my alien the areas are all red, I used the weight paint tools to get a proper painting but I cannot get it to work. When I make a kind of gradient (red in the middle of the bone, brighter colors on the outside) it still does not look good. Can anyone give me some advise or a simple but good tutorial on how to do this. I also attached the blender file so you can take a look yourself:

http://www.2shared.com/file/nhxwjP5r/Animation3.html