Path Finding Algorithms + Animation (Mega Man X Study)

This is based on the spider boss of Mega Man X.  The most interesting feature of that boss was that it would produce a web which is basically a graph, and then in would chose almost at random, a path down the web. I say almost because it would sometimes choose a less efficient path to hitting the player, but other times it would seems to choose the shortest path to the player and that made that boss very interesting to fight and even a bit scary.

So I am trying to reproduce that idea with pygame. What I have so far is a black sprite representing the spider, and green gridblocks representing the traversable web, and red representing not part of the web. If you press 4, the shortest path from the hard coded start position, to the hard coded end position, calculated using the basic shortest path dfs algorithm I recently learned. Then the sprite is updated as with position changes based on stepping through the path list.

This path is from (2,0) to (0,5). (x, y)

Spider at start position.
Spider at start position.
Spider on it's way through shortest path.
Spider on it’s way through shortest path.

Then I have an even more basic find first path algorithm. So if you press 3 the spider sprite will just take that path which is longer.

Spider on longer path 1.
Spider on longer path 1.
Spider on longer path 2.
Spider on longer path 2.
spider5
Spider on longer path 3.
Spider on longer path 4.
Spider on longer path 4.
廣告

Attempts at Path-finding: Some pictures of what I have so far

I have this one graph I generated but it seems to big and finding the shortest path on it just takes way way way too long, I never waited to see how long would actually take. I know there is a way to calculate that but I haven’t learned that yet.

Next is after following this tutorial:        http://programarcadegames.com/index.php?chapter=array_backed_grids

Oh and btw I didn’t follow the tutorial exactly because I try to use classes whenever I can now to get practice. After that I decided to implement path finding with this grid as the basis of a graph. What I need to do tomorrow is use xy tuple coordinates instead of the way I did it which was to add the row and column to try and get an index out of 100. Oh damn I just realized, maybe I need to multiply them instead of add to get an index out of 100 row of 1 to 10 and columns of 1 to 10 yeilds 100 spaces but trying to create indexes by adding the row and column space doesn’t yeild 10o unique positions…iunno I’m tired. lol, so here are the pictures in order of my introductions to them.

The over-sized graph
The over-sized graph
The result of finding just one path on the oversized graph from a start node to an end node.
The result of finding just one path on the oversized graph from a start node to an end node.
The 10X10 grid I turned into a graph and added values 0-2 and colors based on the values. The found a path from 1 -I think 15?
The 10X10 grid I turned into a graph and added values 0-2 and colors based on the values. The found a path from 1 -I think 15?

Attempts at Pathfinding : Argg!!! The little technicalities

I have been spending the last few days wrapping my head around basic path finding with recursion for backtracking, and also stumbled across path finding with just for loops and a queue.

I have been trying to add the path-finding into both my games, and another really interesting idea I have which should actually be easier.

My stumbling points today have actually just been little python technicalities involving dictionaries, tuples, un-hashables, and for row in list meaning “row" is actually part of a list instead of an int making it unhashable in dictionaries if I use the same variable again later etc etc. Stuff like that took up the whole day lol.

Also using a dictionary to hold coordinates as keys and as values for keys has been slow because of the above I guess.

Also just learning the best way to implement a graph and how the map should work with the grid.

Set Builder Notation(Needed to understand Sets and then Markov Models)

References:
http://www.quora.com/What-does-S-x-%E2%88%88-R-2-x-%E2%88%88-0-1-2-mean

https://en.wikipedia.org/wiki/Element_(mathematics)#Notation_and_terminology

http://www.ma.utexas.edu/users/gordanz/notes/introduction_to_stochastic_processes.pdf

S={}: means S is will be a “Set"

R stands for real numbers.

R^2 stands for “real plane" or “Cartesian Plane"

S={xR^2}: Specifies a Universe of Discourse, meaning the type of elements we are interested in, in the set. For example, integer numbers, words, etc.

^2 means “pairs of which" so R^2 means “pairs of real numbers"

S={xR2x[0,1]^2}  Specifies the unierse of discourse and then further specifies the members from that universe that we want in our set which are [0,1] meaning all numbers between 0 and 1.

[0,1]^2 means pairs of 0 and 1

and also I think it’s about coordinates on a Cartesian Plane.

| means add another condition or"such that".

∈ is a symbol that means “in"

I read some of the tutorial in the third link. I feel sick lol.

Markov: The Messy Commented code for reference

from random import choice #allows choice in getnext to chose at random
import sys

def generateModel(text, order): #funtion called generate moddel
model = {} #curly braces in python to define a dictionary
for i in range(0, len(text) – order): #if text is bobby, len is 5, if order is 3,
#5-3 is 2 so the last fragment considered below will be bby(2,3,4) (0-4 is 5 letters)
fragment = text[i:i+order] #i+order so it takes that many letters? bo as frag
#apparently i:i+order starts from i and stops at i+order WITHOUT including it
#so with order = 1, and text = bobby, first fragment will be just b.
next_letter = text[i+order] #the next letter will be i+order. o is next
if fragment not in model:
model[fragment] = {} #if b is first it’s not in model yet so nothing is added
#also more curly braces so this is the inner dictionary
#also square brackets add a value to the dictionary.
if next_letter not in model[fragment]:
model[fragment][next_letter] = 1 #model adds o as a next letter to b and if not
#in model it is assigned a weight of 1
else:
model[fragment][next_letter] += 1 #if either frag or next are letter already in
#the model then the number is incremented.
return model

def getNextCharacter(model, fragment):#so I guess “fragment will be from generate model"
letters = []
for letter in model[fragment].keys():#will look through each fragment and for each key in that fragment…
for times in range(0, model[fragment][letter]):#…the range will be set by the number given to the key
letters.append(letter)#so for the bobby example, b of b is 1 and so it appends b and breaks
return choice(letters)#choice after all the loops will be a random choice out of letters

def generateText(text, order, length):
model = generateModel(text, order)#calls generate model
currentFragment = text[0:order]#again 0:order is up to but not including that index
output = “"#
for i in range(0, length-order):
newCharacter = getNextCharacter(model, currentFragment)#gets weighted random character
output += newCharacter #adds it to output
currentFragment = currentFragment[1:] + newCharacter
print output#change to [1:] above means truncating the character at 0: so you can
#add + newCharacter to fill the fragment again before looping
text = “some sample text"
if __name__ == “__main__": #a main check because the itrpter names a module main
#if it is running as it’s own program
#if someone wanted to use the module in another program
#and call the functions themselves the ifstatement ensures
#the module doesn’t run when accessed.
generateText(text, int(sys.argv[1]), int(sys.argv[2]))
# sys.argv 1 and 2 are what I will pass on running the
#program(text doesn’t need to be passed as it will be defined
#the code. it’s as simple as markov.py 2 5 (2 and 5 being
#order and length respectivly.