Re: [pygame] A* pathfinding demo

[Knapp <magick.crow@xxxxxxxxx>]

                         I wrote this code and then someone else on
the list improved it. It is to test the different methods of distance
calculation. I would love to hear of anything faster.

I was also thinking that with the A* the distance calculations might
all tend to be about the same and maybe a look up table would be
faster there also.

Douglas


#! /usr/bin/env python

from math import *
from time import clock
from random import random

def   distanceA(dx,dy, sqrt=sqrt):          #Pythagorean 1
  return   sqrt(dx**2 +   dy**2)

def   distanceAA(dx,dy):                    # Variant of Pythagorean 1
  return (dx**2 +   dy**2) ** 0.5

def   distanceAAA(dx,dy):                    # Variant of Pythagorean 2
  return (dx*dx +   dy*dy) ** 0.5

def   distanceAAAA(dx,dy):                    # Variant of Pythagorean
3 for comparing which is farther only
  return dx*dx +   dy*dy

def distanceB(dx,dy):#17% faster
   return hypot(dx,dy)

def   distanceC(a,b, atan=atan, sin=sin):   #trig, maybe a lookup
table could speed this up?
  A=atan( a/b)
  return a/sin(A)

def distanceD(a,b, abs=abs, complex=complex):   #complex math that I
don't understand.
	return  abs(complex(a,b))

xlist = [random() for i in xrange(1000000)]
ylist = [random() for i in xrange(1000000)]
for func in [distanceA, distanceAA, distanceAAA, distanceAAAA,
distanceB, distanceC, distanceD]:
    start = clock()
    result = map(func, xlist, ylist)
    end = clock()
    print end-start, func.__name__

> > i made a very small, simple demo showing pathfinding with the A* algorithm.
>
> The math.sqrt(dx*dx+dy*dy) for heuristic distance calculation is not
> necessary. You could just use dx+dy, especially when you do not allow to
> walk on diagonals.