빗자루네

numpy
파이썬에서 고속의 수학 연산을 지원합니다.
http://sourceforge.net/projects/numpy/


SciPy
numpy 를 기반으로 수학이나 과학 문제를 풀 때 쓸만한 유틸리티 모듈입니다. 다양한 인터폴레이션 함수 지원이 매력적입니다.
http://sourceforge.net/projects/scipy/files/


matplotlib
파이썬에서 그래프를 그려주는 모듈입니다.
http://matplotlib.sourceforge.net/

뉴턴 제차분 보간법에 접선을 추가해 정확도를 올린 방법입니다

def __newton_subcalc(sx, sy, ex, ey):

    return (ey - sy)/float(ex - sx)

def __newton_build(srcList, stack):
    """
    x   y
    1   11
    2   12  F[1,2] = (1, 11, 2, 12)
    3   13  F[2,3] = (2, 12, 3, 13) F[1,3] = (1, F[1,1], 3, F[2,3])
    """
    stack.append((srcList[0][2], srcList[-1][2]))

    if len(srcList) <= 1:
        return stack

    sx, mx, sy = srcList[0]
    dstList = []
    for mx, ex, ey in srcList[1:]:
        v = __newton_subcalc(sx, sy, ex, ey)
        dstList.append((sx, ex, v))
        sx, sy = mx, ey
    return __newton_build(dstList, stack)

def __hermite_build(srcList, stack):
    """
    x   y
    1   11
    1   11  F'[1]
    2   12  F[1,2] = (1, 11, 2, 12)
    2   12  F'[2] 
    3   13  F[2,3] = (2, 12, 3, 13) F[1,3] = (1, F[1,1], 3, F[2,3])
    3   13  F'[3]
    """
    stack.append((srcList[0][2], srcList[-1][2]))

    if len(srcList) <= 1:
        return stack

    sx, mx, sy, diff = srcList[0]
    dstList = []
    dstList.append((sx, sx, diff))
    for mx, ex, ey, diff in srcList[1:]:
        dstList.append((sx, ex, __newton_subcalc(sx, sy, ex, ey)))
        sx, sy = mx, ey
        dstList.append((sx, sx, diff))

    return __newton_build(dstList, stack)

def hermite_interpolation(srcList, x):

    # 재귀함수를 호출할때 사용하는 형식으로 데이터를 바꾼다
    srcList = [(cx, cx, cy, diff) for cx, cy, diff in srcList]

    stack = __hermite_build(srcList, [])
    fc, bc = stack[0]

    argList = []
    for src in srcList:
        argList.append(src[0])
        argList.append(src[0])

    fc, bc = stack[0]
    fr = fc
    count = 1
    for fc, bc in stack[1:]:
        arg = argList[0]
        dx = (x - arg)
        for arg in argList[1:count]:
            dx *= (x - arg)
        fr += fc * dx
        count += 1

    revList = [] + argList
    revList.reverse()

    fc, bc = stack[0]
    br = bc
    count = 1
    for fc, bc in stack[1:]:
        arg = revList[0]
        dx = (x - arg)
        for arg in revList[1:count]:
            dx *= (x - arg)

        print "!!", bc*dx
        br += bc * dx
        count += 1


    return fr, br


# x, y, f'(x) 값을 입력합니다.
positions = [
    (1.3, 0.6200860, -0.5220232),
    (1.6, 0.4554022, -0.5698959),
    (1.9, 0.2818186, -0.5811571),
]

print hermite_interpolation(positions, 1.5)

# -*- coding: cp949 -*-
def __newton_subcalc(sx, sy, ex, ey):
    return (ey - sy)/float(ex - sx) # 기울기를 구한다

def __newton_build(srcList, stack):
    """
    x   y
    1   11
    2   12  F[1,2] = (1, 11, 2, 12)
    3   13  F[2,3] = (2, 12, 3, 13) F[1,3] = (1, F[1,1], 3, F[2,3])
    """
    stack.append((srcList[0][2], srcList[-1][2]))

    if len(srcList) <= 1:
        return stack

    sx, mx, sy = srcList[0]
    dstList = []
    for mx, ex, ey in srcList[1:]:
        dstList.append((sx, ex, __newton_subcalc(sx, sy, ex, ey)))
        sx, sy = mx, ey
    return __newton_build(dstList, stack)

def newton_interpolation(srcList, x):
    """
    stack
    P(x) = stack[0] + stack[1](x - x0) 
                           + stack[2](x - x0)(x - x1) 
                           + stack[3](x - x0)(x - x1)(x - x2)
    ...
    
    x 가 리스트 앞쪽에 가까울 때는 전향차분을 사용하고 (왼쪽 리턴값)
    x 가 리스트 뒤쪽에 가까울 때는 후향차분을 사용한다. (오른쪽 리턴값)
    """
    # 재귀함수를 호출할때 사용하는 형식으로 데이터를 바꾼다
    srcList = [(cx, cx, cy) for cx, cy in srcList]

    stack = __newton_build(srcList, [])

    fc, bc = stack[0]
    fr = fc
    count = 1
    for fc, bc in stack[1:]:
        cx, ct, cy = srcList[0]
        dx = (x - cx)
        for cx, ct, cy in srcList[1:count]:
            dx *= (x - cx)
        fr += fc * dx 
        count += 1


    revList = [] + srcList
    revList.reverse()

    fc, bc = stack[0]
    br = bc
    count = 1
    for fc, bc in stack[1:]:
        cx, ct, cy = revList[0]
        dx = (x - cx)
        for cx, ct, cy in revList[1:count]:
            dx *= (x - cx)

        br += bc * dx
        count += 1
    
    return fr, br



positions = [
        (1.0, 0.7651977), 
        (1.3, 0.6200860), 
        (1.6, 0.4554022), 
        (1.9, 0.2818186), 
        (2.2, 0.1103623), 
]

print newton_interpolation(positions, 1.5)

def dot(A, B):
        sum = 0
        for a, b in zip(A, B):
                sum += a * b

        print "dot(%s, %s) = %d" % (A, B, sum)
        return sum

def mul3x4(A, B):
        out = [
                [None for x in xrange(4)]
                        for y in xrange(3)]

        for c in xrange(4):
                B_col = [B[y][c] for y in xrange(3)]
                for r, A_row in enumerate(A):
                        out[r][c] = dot(A_row, B_col)

        return out

a = [
 [2, -3, 1],
 [1, 1, -1],
 [-1, 1, -3]]

b = [
 [ 2, 6,  0, 1],
 [-1, 4,  1, 0],
 [ 0, 5, -3, 0]]

print mul3x4(a, b)

게임에서 선형 보간으로 하면 촌스러운 느낌이됩니다. ~(-_-)~

가속 감속을 주는 방정식을 만들고 싶을때 사용하는
뉴턴 제차분을 이용한 방정식 만들기 프로그램 입니다.

def __newton_subcalc(sx, sy, ex, ey):
    return (ey - sy)/float(ex - sx)

def __newton_build(srcList, stack):
    """
    x   y
    1   11
    2   12  F[1,2] = (1, 11, 2, 12)
    3   13  F[2,3] = (2, 12, 3, 13) F[1,3] = (1, F[1,1], 3, F[2,3])
    """
    stack.append((srcList[0][2], srcList[-1][2]))

    if len(srcList) <= 1:
        return stack

    sx, mx, sy = srcList[0]
    dstList = []
    for mx, ex, ey in srcList[1:]:
        dstList.append((sx, ex, __newton_subcalc(sx, sy, ex, ey)))
        sx, sy = mx, ey
    return __newton_build(dstList, stack)

def newton_gen_polyf_items(srcList):
    srcList = [(cx, cx, cy) for cx, cy in srcList]

    stack = __newton_build(srcList, [])

    fc, bc = stack[0]
    fr = fc

    yield "%f" % (fr)

    count = 1
    for fc, bc in stack[1:]:
        cx, ct, cy = srcList[0]
        yield " * ".join(["%f * (x - %f)" % (fc, cx)] + ["(x - %f)" % (cx) for cx, ct, cy in srcList[1:count]])
        count += 1

def newton_gen_polyb_items(srcList):
    srcList = [(cx, cx, cy) for cx, cy in srcList]

    stack = __newton_build(srcList, [])

    revList = [] + srcList
    revList.reverse()

    fc, bc = stack[0]
    br = bc

    yield "%f" % (br)

    count = 1
    for fc, bc in stack[1:]:
        cx, ct, cy = revList[0]
        yield " * ".join(["%f * (x - %f)" % (bc, cx)] + ["(x - %f)" % (cx) for cx, ct, cy in revList[1:count]])
        count += 1

def newton_make_polyf(positions):
    return " + ".join((expr for expr in newton_gen_polyf_items(positions)))

def newton_make_polyb(positions):
    return " + ".join((expr for expr in newton_gen_polyb_items(positions)))

if __name__ == "__main__":
    positions = [
            (0.0,  0.3),
            (0.33, 0.7),
            (0.66, 0.9),
            (1.0,  1.0),
    ]

    print newton_make_polyf(positions)
    print newton_make_polyb(positions)

게임에서는 최종값이 중요하니 newton_make_polyb 를 사용하는 것이 좋은듯 합니다.

게임을 만들다보면 두점 사이의 방향이나 거리를 구해야 하는 일이 많습니다.
이거 하나 하자고 벡터 클래스 만들기도 귀찮아서 아래와 같은 코드를 작성하곤 했는데...

import math

src = (sx, sy)
dst = (dx, dy)
scale = 2.0

delta = dst[0] - src[0], dst[1] - src[0]
deltaLen = math.sqrt(delta[0] * delta[0], delta[1] * delta[1])
deltaDir = (delta[0] / deltaLen, delta[1] / deltaLen)
newPos = deltaDir[0] * scale, deltaDir[1] * scale

속도는 둘째치고, 코드량의 압박이 장난이 아닙니다.

오늘 몬스터 날리기를 구현하던 도중 불현듯 재밌는 아이디어가 떠오르더군요

바로 복소수!! 입니다.

(x, y) 좌표 연산이나 복소수 연산이나 2차원 연산이라는 점에서 동일하거든요

src = (sx, sy)
dst = (dx, dy)
scale = 2.0

delta = complex(*dst) - complex(*src)
deltaLen = abs(delta)
deltaDir = delta / abs(delta)
newPos = delta / abs(delta) * scale

짠 ~

와하하 너무 좋아요