블로그 이미지
래머
오늘도 열심히 개발하는 개발자입니다.

calendar

1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31

Notice

2014. 5. 4. 22:58 알고리즘

일단 기본알고리즘 구조는 이전의 글에서 설명된 것처럼 굉장히 심플하다.

왜 그렇게 되는지 이해하는 문제는 물론 별개의 문제이지만.


1. A* 알고리즘이란?

 

A* 알고리즘은 초기노드(시작지점)에서 목표 노드(목표지점)까지의 경로를 찾는 그래프 탐색 알고리즘이다. 다른 그래프 탐색 알고리즘과 다른 점은 목표에 얼마나 근접한 것인지를 평가하는데 휴리스틱 함수를 사용한다는 것이다.

 

 

2. 알고리즘 순서

 

(1) 시작지점을 열린목록(Openlist)에 넣는다.

(2) 열린목록에 있는 노드 중 1개를 빼서 여덟 방향 주변노드를 탐색한다.
( 평가함수 F= G+H 를 계산 & 부모노드를 명시, 장애물과 닫힌목록은 제외한다.)
F= G+H 설명
G : 시작노드N0에서 현재노드N까지의 최단경로의 값. (수직,수평 +1, 대각선일 경우 +1.41)
H : 현재노드N에서 목표노드까지의 (조건없는)최단경로의 값. (휴리스틱요소)
F :  시작노드N0에서 목표노드까지 현재노드N을 통해 갈 수 있는 모든 가능한 경로 중  최단경로의 값이 된다.

(3) 2단계에서 뺀 노드를 닫힌목록(Closelist)에 삽입한다

(4) 2단계에서 탐색한 노드들을 열린 목록(우선순위 queue)에 삽입한다
(우선순위 큐는 가장 작은 값부터 순서대로 자동정렬되는 특성을 가지기 때문에 가장 낮은 F비용을 가진 노드를 찾을 수 있다.)

(5) 열린 목록 중 가장 앞 노드를 빼고 그 노드를 닫힌 목록에 추가한다.

(6) 5단계에서 뺀 노드의 여덟방향 주요 노드를 탐색한다.
(장애물과 닫힌목록제외, 목표노드가 있는지 조사)
(끝내는 경우: 1. 만일 목표노드가 있다면 부모노드를 추적하여 역순으로 스택에 삽입 2. 열린목록이 비어있게 될 경우 목표노드를 찾는데 실패한 것, 길이 없음.)

(7) 열린목록에 존재하지 않는 노드는 열린목록에 추가하고
중복되는 노드는 G값을 서로비교하여 더 작은 값을 열린 목록으로 교체한다.

(8) 5단계부터 반복

[출처] A* 알고리즘|작성자 김도완


c#언어를 사용해서 구현해보도록 하겠다.

일단 위의 순서부분에 나와 있는 것들을 하나씩 구현해보고 실제 동작을 하는지 확인해본다.




위에 그림은 실제 A*알고리즘을 구현해본 프로그램의 스크린샷이다.

파란색 네모는 고양이를 녹색 네모는 쥐들을 나타내고, 빨간색 영역은 갈수 없는 곳을 노란색 영역은 갈 수 있는곳을 나타낸다.

기본적으로 쥐들은 고양이가 가까이 오게되면 화면의 임의의 위치를 정해서 도망을 가도록 되어 있다.

마우스 왼버튼 클릭으로 고양이의 위치를 지정하게 되면 구현된 A*알고리즘에 따라서 해당 위치의 경로를 탐색하게 되고 

경로가 찾아진 경우에는 해당 위치로 이동하게 된다. 만일 고양이의 이동경로에 취들이 있다면 취들은 혼비백산해서 맵의 임의의

위치로 역시 A*알고리즘을 사용해서 경로 탐색을 한다음에 이동하게 될것이다.


먼저 위에 있는 A*알고리즘의 작동순서에 따라서 구현하기 위해서 필요한 것들이 있다.


열린노드, 닫힌노드, 그리고 실제 길을 구성하는 맵데이터가 그것이다.


열린노드와 닫힌 노드는 단일 연결리스트로 구현한다.

다음과 같은 구조로 선언했다.


public class CNaviNode

    {
        public int x, y; //위치, 2D맵으로 표현하기 위한 위치
        public int dist; //목표점까지의 거리
        public int depth; 

        public CNaviNode pParent = null;

//현재 노드를 주어진 노드의 내용물로 복사
        public void Copy(CNaviNode pNode)
        {
            x = pNode.x;
            y = pNode.y;
            dist = pNode.dist;
            depth = pNode.depth;
            pParent = pNode.pParent;
        }

//위치가 같은지 확인 public bool IsSamePos(CNaviNode pNode) { if (x != pNode.x || y != pNode.y) return false; return true; }

//내용물을 그대로 복사 public CNaviNode Clone() { CNaviNode pNode = new CNaviNode(); pNode.x = x; pNode.y = y; pNode.dist = dist; pNode.depth = depth; pNode.pParent = null; return pNode; }

//노드의 위치를 sx, sy로 설정하고, 목표점 dx, dy까지의 거리를 구해서 초기화 한다. , dep는 탐색깊이 public static CNaviNode Create(int sx, int sy, int dx, int dy, int dep) { CNaviNode pNode = new CNaviNode(); pNode.x = sx; pNode.y = sy; int deltx = dx - sx; int delty = dy - sy; pNode.dist = (deltx * deltx) + (delty * delty); pNode.depth = dep; return pNode; }

//단순히 시작점 sx, sy로 해서 노드를 생성한다 public static CNaviNode Create(int sx, int sy) { CNaviNode pNode = new CNaviNode(); pNode.x = sx; pNode.y = sy; return pNode; }

//주어진 목표점 까지의 거리를 구하고 탐색깊이를 설정한다. public void CalcDist(CNaviNode pDest, int cdepth) { int deltx = pDest.x - x; int delty = pDest.y - y; dist = (deltx * deltx) + (delty * delty); depth = cdepth; } public void SetParent(CNaviNode p) { pParent = p; } public CNaviNode GetParent() { return pParent; } }


길을 구성하는 맵데이터는 단순히 바이트 배열로 선언하고, 갈수 없는부분은 0으로

갈수 있는곳은 1로 마킹하여 텍스트 파일로 저장했다.

아래가 실제 맵데이터이며, 맵의 폭과 높이에 대한 정보와 실제 맵에서 갈 수 있는곳과 없는곳을 표현한 

데이터이다.

width 40

height 40

mapstart

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1

1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1

1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1

1 1 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1

1 1 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1

1 1 1 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1

1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1

1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1



실제 길찾기 수행하기

class CAStarPathFinding

    {

        private List<CNaviNode> m_vecOpenNode = null;        //열린노드

private List<CNaviNode> m_vecCloseNode = null;    //닫힌노드

public void Delete()

{

m_vecOpenNode = null;

m_vecCloseNode = null;

m_vecOpenNode = new List<CNaviNode>();

m_vecCloseNode = new List<CNaviNode>();

}


        //시작 위치 PStart에서 목표위치 pEnd까지의 경로를 구한다. 경로가 구해진경우 true그렇지 않은경우 fale

        //vecPath : 구해진경로

        //pNavi : 지형데이터를 제공한다, 위의 맵데이터를 읽어서 맵에 대한 컨트롤 정보를 제공한다

public bool FindPath(CNaviNode pStart, CNaviNode pEnd, ref List<CNaviNode> vecPath, CNavigationData pNavi)

{

Delete(); //열린노드 및 닫힌노드 정보를 클리어하고 초기화


CNaviNode pNode = pStart.Clone();

/*

* insert start position to open node, 시작점을 열린노드에 삽입한다.

* */

m_vecOpenNode.Add(pNode);


int iDepth = 0;

pNode.depth = iDepth;


List<CNaviNode> vecChilds;

vecChilds = new List<CNaviNode>();

while(true)

{

if (m_vecOpenNode.Count == 0)

{//if opennode has not contents, it's meaning that path not found. 만일 열린노드에 더이상 데이터가 없다면 길이 존재하지 않는것이다.

break;

}




pNode = m_vecOpenNode[0]; //get first content, 열린노드의 가장처음항목을 하나 가져온다

m_vecOpenNode.RemoveAt(0); //delete content from open node, 가져온것은 열린노드에서 제거한다


if (pEnd.IsSamePos(pNode)) //if that node is end position, we found path, 만일 가져온 노드가 목표점이라면 해당 노드를 패스목록에 추가하고 길탐색을 종료한다

{

while(pNode != null) //tracking it's parent node for it's parent is null

{

vecPath.Add(pNode); //add node to path list

pNode = pNode.GetParent(); //get current node's parent

}


return true;

}


pNode = InsertCloseNode(pNode); //insert current node to close list, 목표점이 아니면 해당 노드를 닫힌노드에 삽입한다.



                ++iDepth; //탐색깊이를 하나 증가 시킨다

vecChilds.Clear(); 

pNavi.GetNeighbor(pNode, ref vecChilds);    //해당노드의 인접한 노드들을 모두 가져와서


for (int i = 0;i < vecChilds.Count; ++i)

{

if (FindFromCloseNode(vecChilds[i]))    //만일 닫힌노드에 있는것이면 무시하고

{

continue;

}


                    //닫힌노드에 없는것이라면, 거리를 구한다음에 열린노드에 삽입한다.

vecChilds[i].CalcDist(pEnd, iDepth);

vecChilds[i].SetParent(pNode);

InsertOpenNode(vecChilds[i]);

}


                //열린노드를 비용에 따라서 정렬한다

SortOpenNode();

}


Delete();

return false;

}


        //노드 p1이 노드 p2보다 저비용이라면(거리가 더가까우며, 탐색깊이가 더 작은지) true

private bool NodeCompare(CNaviNode p1, CNaviNode p2)

{

if (p1.dist < p2.dist) return true;

if (p1.dist > p2.dist) return false;

if (p1.depth <= p2.depth) return true;

return false;

}


        //열린노드에 노드 삽입, 중복된 노드가 삽입되지 않도록 처리한다

private void InsertOpenNode(CNaviNode pNode)

{

for (int i = 0;i < m_vecOpenNode.Count; ++i)

{

if (m_vecOpenNode[i].IsSamePos(pNode))

{

InsertCloseNode(m_vecOpenNode[i]);

m_vecOpenNode[i] = pNode;

return;

}

}


m_vecOpenNode.Add(pNode);

}


        //닫힌노드에 삽입

private CNaviNode InsertCloseNode(CNaviNode pNode)

{

m_vecCloseNode.Add(pNode);

return pNode;

}


        //열린 노드를 비용에 따라서 정렬한다, 심플하게 버블정렬을 하고 있다.

private void SortOpenNode()

{

if (m_vecOpenNode.Count < 2) return;

CNaviNode pNode;


bool bContinue = true;


while(bContinue)

{

bContinue = false;

for (int i = 0;i < m_vecOpenNode.Count - 1; ++i)

{

if (!NodeCompare(m_vecOpenNode[i], m_vecOpenNode[i+1]))

{

pNode = m_vecOpenNode[i];

m_vecOpenNode[i] = m_vecOpenNode[i+1];

m_vecOpenNode[i+1] = pNode;

bContinue = true;

}

}

}

}



        //열린노드에 해당 노드가 있는지 확인한다

private bool FindFromOpenNode(CNaviNode pNode)

{

for (int i = 0;i < m_vecOpenNode.Count; ++i)

{

if (m_vecOpenNode[i].IsSamePos(pNode)) return true;

}

return false;

}


        //닫힌노드에 해당 노드가 있는지 확인한다

private bool FindFromCloseNode(CNaviNode pNode)

{

for (int i = 0;i < m_vecCloseNode.Count; ++i)

{

if (m_vecCloseNode[i].IsSamePos(pNode)) return true;

}

return false;

}

    }


전체 프로젝트 소스코드는 첨부파일에서 다운로드 가능하다.



pathtest2.zip




'알고리즘' 카테고리의 다른 글

쿼터니언  (0) 2014.05.02
A* 알고리즘이란?  (0) 2014.05.02
posted by 래머
2014. 5. 4. 11:13 기타

출처 sharbong의 무한 삽질시작 | 샤르봉

원문 http://blog.naver.com/sharbong/100003379773

요즘 시도하는 것이 자꾸 날 실망시키는 관계로 우울함이 극상을 달리고있는 이때.

기분전환삼아서 캐릭터 애니매이션 2를 써본다.

 

첫번째 글에서 나는 본애니의 기본적인 방법에 관해서 이야기 했다.

그때 본애니에서는 스티칭 애니와 스키닝 애니  두개가 있다고 한 기억이 있다. ( 없나? )

뭐 하여간 오늘은 스티칭 애니의 대표적인 파일포멧인 SMD에 관해서 살짝 이야기 하겠다.

잠시 스티칭 애니에 관해서 살짝 이야기 하고 가겠다.

 

스티칭 애니는 점 하나에 본하나가 영향을 주는 형태를 말한다.

그때문에 관절부분이 애니때 접힌다면, 뽀족하게 될 소지가 높다.

하지만 버텍스하나에 매트릭스 하나이기에 속도는 빠르다.

(그림정보를 찾으려다 귀차니즘의 압박으로 그만두도록하자. 뭐 보는 사람이 있을지도 의문이니...)

 

참고로 SMD로 본애니를 공부했지만, 의외로 국내에서 SMD를 쓰는 사람과 회사들이 많다는거다.

( 뮤가 SMD로 만들었다....신기할 따름이다. )

SMD는 벨브사가 하프라이프 SDK를 공개하면서 같이 공개된 포멧이다.

( ...아닌가? 분명 벨브사가 만든것만은 분명하다. )

 

SMD의 장점은 군더더기가 없는 매우 명료한 정보들만 가지고 있다는 것이다.

그때문에 단점은 너무 군더더기가 없어서, 몇개가 있는지조차 가르쳐주지 않는다는거다.

( 본의 갯수라던가, 삼각형의 갯수등등... )

 

MOD파일을 보면 SMD말고 해더성 정보파일이 하나더 있는데, 그런식으로 관리하려고 뺀듯하다.

 

SMD의 자료구조는 크게 3부분으로 나뉜다.

본노드 / 스켈레톤 정보 / 매쉬 정보

 

이런 정보를 가지는 SMD는 두가지 포멧으로 나뉘어진다.

레퍼런스와 애니메이션.

 

레퍼런스에는 위의 3가지 자료구조를 모두 가지고 있다. 말그대로 레퍼런스로서 본과 본정보,

그리고 매쉬가 존재하는 것이다.

 

애니메이션은 위 3가지 정보중, 매쉬정보가 빠져있으며, 스켈레톤 정보가 프레임수만큼 나와있다.

여기서 살짝 smd를 보자.

 

version 1
nodes
  0 "Bip01"  -1
  1 "Bip01 Footsteps"   0
  2 "Bip01 Pelvis"   0
  3 "Bip01 L Leg"   2
  4 "Bip01 L Leg1"   3

  ....


skeleton
time 0
  0 0.000000 -0.000000 39.526119 0.000000 0.000000 -1.570795
  1 0.000000 0.000000 -39.332325 0.000000 0.000000 1.570795
  2 0.866404 0.000000 0.000000 -1.570795 -1.570796 0.000000
  3 -0.000005 0.000007 3.713254 0.002054 3.115505 -0.021473
  4 18.045723 -0.000000 -0.000000 0.000000 -0.000000 -0.121501

  .....


triangles
PLAYER_Chrome1.bmp
 20   6.2915   3.6852  58.7875   0.7828   0.5264   0.3317   0.0137   0.2611
 44   5.8005  -1.2928  62.2638   0.1754   0.2434   0.9539   0.0948   0.4558
 44   7.4334   2.4543  59.8983   0.1717   0.8248   0.5387   0.0317   0.3338
PLAYER_Chrome1.bmp
 19   3.9185   3.2071  51.5657   0.6297   0.6813  -0.3732  -0.1638   0.3040
 44   7.4334   2.4543  59.8983   0.1717   0.8248   0.5387   0.0317   0.3338
 44   8.0542   2.2868  54.9256   0.5291   0.7574  -0.3827  -0.0604   0.3564
PLAYER_Chrome1.bmp
 56  -7.4701   2.4393  59.9100  -0.2332   0.7523   0.6162   0.4673   0.3301
 56  -6.0121  -1.2665  62.3253  -0.1773   0.0557   0.9826   0.4038   0.4548
 20  -5.6520   1.8873  62.6681  -0.8312   0.0346   0.5549   0.3928   0.3307
 .....

 

이것이 바로 SMD의 파일구조다.

Nodes가 바로 본의 구조를 나타낸다.

 

  0               "Bip01"       -1

자신인덱스    본이름       부모인덱스

 

이런 형태로 본(트리)구조를 알려준다. 뭐 더이상 설명이 필요없을듯 하다.

 

다음은  skeleton


time 0   <- 레퍼런스라면 time 0 만 존재하지만 애니매이션이라면 애니 프레임수만큼 나올것이다.


  0                 0.000000 -0.000000 39.526119  0.000000 0.000000 -1.570795
자신인덱스    |-----부모의 상대위치------||-----오일러 X Y Z 회전----|

 

이 정보가 바로 실질적인 본의 매트릭스 정보를 말해준다.

1에서 이야기 했듯이 본노드는 부모로부터의 상대TM을 갖는다고 했다.

저정보들은 모두 부모로부터의 상대값만 가지고 있다. 위치도 회전도 말이다.

저 정보를 매트릭스화 할때 주의할점이 있다. 바로 곱하는 순서다.

저 정보를 매트릭스로 만드는 것을 잘 알고 있을것이다.

부모의 상대위치를 T라 하고 오일러 X Y Z는 각각 Rx RY Rz 라 할때 곱하는 순서는

Rx * Ry * Rz * T 순이다.

참고로 저 순서는 D3D에서의 순서다. OGL이라면 반대로 T * Rz * Ry * Rx 이다.

또한 오일러 회전의 각 축의 각도는 라디안 값이니 OGL이라면 다시 각도로 변환시켜야 할 것이다.

( OGL는 회전을 각도로 받고 D3D는 라디안 값으로 받는다. )

저렇게 해서 만들어지는 저 노드의 자기 TM이다.

부모가 있을때는 자기TM * 부모TM 순으로 곱해야 한다.

( 역시 OGL이라면 반대로 부모가 앞에 온다. )

 

이제 마지막 triangles


PLAYER_Chrome1.bmp  <- 이 삼각형이 사용하는 텍스쳐명이다.

 

아래 순서대로 삼각형을 구성한다.
 20   6.2915   3.6852  58.7875   0.7828   0.5264   0.3317   0.0137   0.2611
 44   5.8005  -1.2928  62.2638   0.1754   0.2434   0.9539   0.0948   0.4558
 44   7.4334   2.4543  59.8983   0.1717   0.8248   0.5387   0.0317   0.3338

자 이제 점정보를 보자.

 20                 6.2915   3.6852  58.7875   0.7828   0.5264   0.3317   0.0137   0.2611
영향본인덱스   버텍스 x y z                   노멀 x y z                    텍셀 u v

 

위에서 스티칭 애니는 하나의 본에 영향을 받는 구조라고 말했다.

버택스 하나가 본하나에 1:1 매칭된다는 것은 속도가 빠르다.

물론 스키닝 애니에 비해서일뿐이다. 순수 버택스 애니에 비하면 느릴수밖에 없다.

 

자 일단 SMD에 관해서 설명을 했다. SMD설명을 봐서 알겠지만, 처음에 말했듯이

뭐가 몇개있는지에 대한 정보가 전혀없다. 따라서 SMD를 읽어서 쓸때는 약간의

최적화가 필요하다.

첫번째가 텍스쳐, 같은 이름의 텍스쳐는 같은 텍스쳐인것이 당연하다.

두번째가 버텍스 인덱스화. 저래보여도 중복되는게 꽤 존재한다.

 

자 그럼 오늘은 여기까지.

보고 도움되는 사람이 있을지 의문이다. ( 보는 사람이 있는지도 의문이다. ㅡ.ㅡ )

그럼 오늘도 안녕히.

 

 

ps : 라이트맵이 싫어진다.




posted by 래머
2014. 5. 4. 11:11 기타



[본문스크랩] 하프라이프 mdl 파일포멧과 3d모델구조 낙서장

2007/01/05 08:35 수정 삭제

복사 http://blog.naver.com/choi98772/130013023537

전용뷰어 보기

첨부파일 (1)

출처 카페 > 게임 모델링 에 관한 모든것.. | 늘바나
원문 http://cafe.naver.com/moduser/461

하프라이프 mdl 파일포멧과 3d모델구조 설명




mdl파일구조.rar





posted by 래머
2014. 5. 4. 11:07 기타
출처 카페 > 게임 모델링 에 관한 모든것.. | 늘바나
원문 http://cafe.naver.com/moduser/75

SMD파일은 2개의 버전으로 구성 -> Reference , Animation file로 구성

 

공통구성data : bone의 node구성

Reference   : 0프레임의 bone position/rotation data triangle,

texture map data

Animation   : 모든 프레임의 bone position/rotation data

 

섹션별 구성

Header 

 Version 1 버전을 표시

 

Node tree 

뼈의 모든 본의 목록을 나타낸다.

부모가 없는 Objects는 부모의 ID가 1이다.

 

nodes

<ID> Bone Name <Parent ID>

end

 

Skeleton Pose

뼈 구조의 모든 본들의 position/rotation값들로 구성

Animation SMD는 매프레임마다 time블럭으로 저장

Reference SMD는 첫 프레임의 한 타임만 저장

 

Skeleton

Time 0

<ID><PosX><PosY><PosZ><RotX><RotY<RotZ>

<ID> ® Bone index,

<PosX><PosY><PosZ> ® 월드 좌표계에서의 위치값

<RotX><RotY<RotZ> ® Local Euler 라디안 회전값,부모의 local space의 회전값

Reference SMDs  이 프레임만 출력

Time 1

end

// Animation SMD 여기까지 출력

 

Triangle block

Triangles 리스트만 포함

 

Triangles

bitmapname.bmp

<Parent><PosX><PosY><PosZ><NormX><NormY><NormZ><TexU><TexV>

<Parent> ® vertex의 부모 bone의 ID번호

<PosX><PosY><PosZ>  ® 월드 좌표계에서의 vertex위치값

<NormX><NormY><NormZ> ® 스무싱을 위한  vertex normal vector

<TexU><TexV> ® vertex의 texture 좌표값

버텍스 3개씩 기록

 

nextBitmapName.bmp

새로운 triangle리스트 기록

..

end




posted by 래머
2014. 5. 4. 11:05 기타

퀘이크2 의 MD2파일을 로드하거라 압축된 PAK파일로 부터 MD2파일을 볼수 있게

해주는 프로그램이다.

출처 http://www.milkshape3d.com/




md2viewer14-choi98772.zip




posted by 래머
2014. 5. 4. 11:02 기타

하프라이프 게임에서 사용된 모델을(MDL파일) 보여주는 프로그램이다.

PAK으로 압축된 파일도 읽을수 있게 되어있다.

출처 : http://www.milkshape3d.com


hlmv125-choi98772.zip




posted by 래머
2014. 5. 4. 00:05 c#

class CMyTime

    {

        private long m_lOld = DateTime.Now.Ticks;


//현재 시간 캡쳐

        public void Catch()

        {

            m_lOld = DateTime.Now.Ticks;

        }


//마지막으로 시간을 캡쳐한 때로 부터 이 함수를 호출할때까지 경과한 시간을 틱단위로 얻음

        public long GetPassedTime()

        {

            return (DateTime.Now.Ticks - m_lOld);

        }


//마지막으로 시간을 캡쳐한 때로 부터 이 함수를 호출할때까지 경과한 시간을 초단로 얻음

        public float GetSecond()

        {

            return (float)((DateTime.Now.Ticks - m_lOld) * 0.0000001f);

        }


//해당 틱이 몇초에 해당하는 지

        static public float ToSecond(long lTick)

        {

            return ((float)(lTick) * 0.0000001f);

        }


        /// <summary>

        /// 현재의 요일 정보 얻기

        /// </summary>

        /// <returns></returns>

        public static DayOfWeek GetDayofWeek()

        {

            return DateTime.Now.DayOfWeek;

        }

    }




'c#' 카테고리의 다른 글

네이버 앱스토어 인앱영수증 검증 c#버전  (0) 2015.09.13
c#에서 자바의 ByteBuffer 구현하기  (0) 2014.05.05
c# web safe base64  (0) 2014.05.02
posted by 래머
2014. 5. 3. 23:52 iOS


유니티에서 사용하고자 하는경우 아래 코드를 추가하시고
InitCertificateValidationCallback()을 영수증 검증 루틴 실행전 한번 호출해줄필요가 있습니다.

public static void InitCertificateValidationCallback()
        {
            ServicePointManager.ServerCertificateValidationCallback += new System.Net.Security.RemoteCertificateValidationCallback(ValidateServerCertificate);
        }

        static bool ValidateServerCertificate(object sender, System.Security.Cryptography.X509Certificates.X509Certificate certificate, X509Chain chain, SslPolicyErrors sslPolicyErrors)
        {
            return true;
        }

iOS인앱 결제 후 영수증 검증 루틴이다.

첨부된 JSON라이브러리를 c#프로젝트의 참조에 추가할 필요가 있다.

VerifyIOSReceipt 메소드의 리턴값을 판별해서 

처리하면된다.


IOS_RV_SUCCESS = 영수증 검증 성공

IOS_RV_FAIL_RETRY  = 영수증 검증에 실패 했다, 샌드박스모드에서 다시 검증이 필요하다.

IOS_RV_FAIL  = 유효하지 않은 영수증이다.


using System.Text;

using System.Net;

using System.IO;

using Newtonsoft.Json;

using Newtonsoft.Json.Linq;

using System;


public class CIOSReceiptVerificationMng

{

    public const string IOS_PRODUCT_URL = "https://buy.itunes.apple.com/verifyReceipt";

    public const string IOS_SENDBOX_URL = "https://sandbox.itunes.apple.com/verifyReceipt";


    public const int IOS_RV_SUCCESS = 0;    //ios영수증 검증 결과 성공

    public const int IOS_RV_FAIL_RETRY = 1;    //샌드박스에서 재검증필요

    public const int IOS_RV_FAIL = -1;    //검증 실패


    /*ios영수증 검증

itemID = 해당 영수증으로 결제한 아이템의 ID

receiptData = 영수증 데이터

bProduct = 프로덕트에서 검증할지 샌드박스에서 검증할지, 기본적으로 프로덕트에서 검증하고 리턴값이 IOS_RV_FAIL_RETRY  인경우에 샌드박스에서 검증한다.

*/

    public static int VerifyIOSReceipt(ref string itemID, string receiptData, bool bProduct)

    {

        try

        {

            itemID = null;


            // Verify the receipt with Apple

            string postString = string.Format("{{ \"receipt-data\" : \"{0}\" }}", receiptData);

            ASCIIEncoding ascii = new ASCIIEncoding();

            byte[] postBytes = ascii.GetBytes(postString);

            HttpWebRequest request;


            if (bProduct)

                request = WebRequest.Create(IOS_PRODUCT_URL) as HttpWebRequest;

            else

                request = WebRequest.Create(IOS_SENDBOX_URL) as HttpWebRequest;


            request.Method = "POST";

            request.ContentType = "application/json";

            request.ContentLength = postBytes.Length;

            Stream postStream = request.GetRequestStream();

            postStream.Write(postBytes, 0, postBytes.Length);

            postStream.Close();


            HttpWebResponse response = request.GetResponse() as HttpWebResponse;

            StringBuilder sb = new StringBuilder();

            byte[] buf = new byte[8192];

            Stream resStream = response.GetResponseStream();

            string tempString = null;


            int count = 0;


            do

            {

                count = resStream.Read(buf, 0, buf.Length);

                if (count != 0)

                {

                    tempString = Encoding.ASCII.GetString(buf, 0, count);

                    sb.Append(tempString);

                }

            } while (count > 0);


            var fd = JObject.Parse(sb.ToString());


            try

            {

                resStream.Close();

                response.Close();

            }

            catch

            {

            }


            string strResult = fd["status"].ToString();

            // Receipt not valid

            if (strResult != "0")

            {

                if (strResult == "21007")

                    return IOS_RV_FAIL_RETRY;


                // Error out

                return IOS_RV_FAIL;

            }


            // Product ID does not match what we expected

            var receipt = fd["receipt"];


            /*

            if (String.Compare(receipt["product_id"].ToString().Replace("\"", "").Trim(), itemID.Trim(), true) != 0)

            {

                // Error out

                return IOS_RV_FAIL;

            }

             * */


            //제품 ID정보를 저장함

            itemID = receipt["product_id"].ToString().Replace("\"", "").Trim();


            // This product was not sold by the right app

            if (String.Compare(receipt["bid"].ToString().Replace("\"", "").Trim(), PACKAGE_NAME, true) != 0)

            {

                // Error out

                return IOS_RV_FAIL;

            }


            /*

            // This transaction didn't occur within 24 hours in either direction; somebody is reusing a receipt

            DateTime transDate = DateTime.SpecifyKind(DateTime.Parse(receipt["purchase_date"].ToString().Replace("\"", "").Replace("Etc/GMT", "")), DateTimeKind.Utc);

            TimeSpan delay = DateTime.UtcNow - transDate;

            if (delay.TotalHours > 24 || delay.TotalHours < -24)

            {

                // Error out

                return false;

            }

            */


            // Perform the purchase -- all my purchases are server-side only, which is a very secure way of doing things

            // Success!

        }

        catch// (Exception ex)

        {

            // We crashed and burned -- do something intelligent

            return IOS_RV_FAIL;

        }


        return IOS_RV_SUCCESS;

    }


}


Newtonsoft.Json.dll


Newtonsoft.Json.xml





'iOS' 카테고리의 다른 글

앱스토어 가이드라인  (0) 2015.10.10
iOS사파리 브라우져를 열어서 특정 사이트로 이동  (0) 2014.05.05
posted by 래머
2014. 5. 3. 23:43 안드로이드

첨부된 바운시캐슬 암호화 라이브러리를 참조에 추가하고 사용해야 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
using System;
 
using System.Security.Cryptography;
 
using System.IO;
 
using System.Text;
 
using System.Xml;
 
using System.Collections.Generic;
 
using System.Linq;
 
using Org.BouncyCastle.Security;
 
using Org.BouncyCastle.Crypto;
 
using Org.BouncyCastle.Crypto.Parameters;
 
 
 
 
/*
사용법
GoogleSignatureVerify gsv = new GoogleSignatureVerify("발급받은 API키");
if (gsv.Verify("결제데이터", 사인데이터))
{
//성공시 처리
}
*/
 
public class GoogleSignatureVerify
 
    {
 
        RSAParameters _rsaKeyInfo;
 
 
 
 
        public GoogleSignatureVerify(String GooglePublicKey)
 
        {
 
            RsaKeyParameters rsaParameters = (RsaKeyParameters)PublicKeyFactory.CreateKey(Convert.FromBase64String(GooglePublicKey));
 
 
 
 
            byte[] rsaExp = rsaParameters.Exponent.ToByteArray();
 
            byte[] Modulus = rsaParameters.Modulus.ToByteArray();
 
 
 
 
            // Microsoft RSAParameters modulo wants leading zero's removed so create new array with leading zero's removed
 
            int Pos = 0;
 
            for (int i = 0; i < Modulus.Length; i++)
 
            {
 
                if (Modulus[i] == 0)
 
                {
 
                    Pos++;
 
                }
 
                else
 
                {
 
                    break;
 
                }
 
            }
 
            byte[] rsaMod = new byte[Modulus.Length - Pos];
 
            Array.Copy(Modulus, Pos, rsaMod, 0, Modulus.Length - Pos);
 
 
 
 
            // Fill the Microsoft parameters
 
            _rsaKeyInfo = new RSAParameters()
 
            {
 
                Exponent = rsaExp,
 
                Modulus = rsaMod
 
            };
 
        }
 
 
 
 
        public bool Verify(String Message, String Signature)
 
        {
 
            using (RSACryptoServiceProvider rsa = new RSACryptoServiceProvider())
 
            {
 
                rsa.ImportParameters(_rsaKeyInfo);
 
                return rsa.VerifyData(Encoding.ASCII.GetBytes(Message), "SHA1", Convert.FromBase64String(Signature));
 
            }
 
        }
 
    }
 
 
 
cs

BouncyCastle.Crypto.dll

유니티를 사용하신다면 아래 유니티 패키지를 임포트 하시면 바운시 캐슬 라이브러리소스가 임포트됩니다.


BouncyCastle.unitypackage



posted by 래머
2014. 5. 3. 23:11 안드로이드
유니티에서 사용하고자 하는경우 아래 코드를 추가하시고
InitCertificateValidationCallback()을 영수증 검증 루틴 실행전 한번 호출해줄필요가 있습니다.

public static void InitCertificateValidationCallback()
        {
            ServicePointManager.ServerCertificateValidationCallback += new System.Net.Security.RemoteCertificateValidationCallback(ValidateServerCertificate);
        }

        static bool ValidateServerCertificate(object sender, System.Security.Cryptography.X509Certificates.X509Certificate certificate, X509Chain chain, SslPolicyErrors sslPolicyErrors)
        {
            return true;
        }

c#으로 작성된 서버 또는 유니티 등에서 티스토어의 인앱 결제 영수증 검증을 다음과 같이 하면된다.



readonly string TSTORE_RECEIPT_VERIFY_URL_PRODUCT = "https://iap.tstore.co.kr/digitalsignconfirm.iap";  //실서비스용서버주소

        readonly string TSTORE_RECEIPT_VERIFY_URL_DEV = "https://iapdev.tstore.co.kr/digitalsignconfirm.iap"; //개발용서버주소

        readonly string TSTORE_RECEIPT_VERIFY_FORMAT = "{{\"txid\" : \"{0}\", \"appid\" : \"{1}\", \"signdata\" : \"{2}\"}}";

        //TStore 영수증 검중구현, 

//bProduct : 서비스/개발용 서버중 어느 서버에서 검증할지

//strAppID : 티스토어에 배포한 프로그램에 할당받은 ID

//strTXID : 인앱 결제후 결과 값으로 넘어온 것중 txid

//strReceipt : 인앱결제 후 결과 값으로 넘어온 영수증 정보

//리턴값이 true인경우 영수증검증에 성공한것이다.

//애플의 영수증을 검증하는 것처럼 먼저 bProduct에 true를 해서 영수증검증을 해보고 만일 실패 하는경우

//false를 줘서 검증을 시도하도록 하면 된다.

        bool VerifyTStoreReceipt(bool bProduct, string strAppID, string strTXID, string strReceipt)

        {

            try

            {

                // Verify the receipt with Apple

                string postString = String.Format(TSTORE_RECEIPT_VERIFY_FORMAT, strTXID, strAppID, strReceipt);

                ASCIIEncoding ascii = new ASCIIEncoding();

                byte[] postBytes = ascii.GetBytes(postString);

                HttpWebRequest request;


                if (bProduct)

                    request = WebRequest.Create(TSTORE_RECEIPT_VERIFY_URL_PRODUCT) as HttpWebRequest;

                else

                    request = WebRequest.Create(TSTORE_RECEIPT_VERIFY_URL_DEV) as HttpWebRequest;


                request.Method = "POST";

                request.ContentType = "application/json";

                request.ContentLength = postBytes.Length;

                Stream postStream = request.GetRequestStream();

                postStream.Write(postBytes, 0, postBytes.Length);

                postStream.Close();


                HttpWebResponse response = request.GetResponse() as HttpWebResponse;

                StringBuilder sb = new StringBuilder();

                byte[] buf = new byte[8192];

                Stream resStream = response.GetResponseStream();

                string tempString = null;


                int count = 0;


                do

                {

                    count = resStream.Read(buf, 0, buf.Length);

                    if (count != 0)

                    {

                        tempString = Encoding.ASCII.GetString(buf, 0, count);

                        sb.Append(tempString);

                    }

                } while (count > 0);


                var fd = JObject.Parse(sb.ToString());


                try

                {

                    resStream.Close();

                    response.Close();

                }

                catch

                {

                }


                string strResult = fd["status"].ToString();

                string strDetail = fd["detail"].ToString();


                // Receipt not valid

                if (strResult == null || strResult != "0" || strDetail == null || strDetail != "0000")

                {

#if DEBUG

                    CLogMng.Instance().Debug("tstore purchase failed : " + sb.ToString());

                    CLogMng.Instance().Debug("txid : " + strTXID);

                    CLogMng.Instance().Debug("signdata : " + strReceipt);

#endif

                    return false;

                }

            }

            catch// (Exception ex)

            {

                // We crashed and burned -- do something intelligent

                return false;

            }


            return true;

        }




posted by 래머