AstarAlgorithm
UserPreferences
serious-code.net
RecentChanges
±â¼úÀÚ·á
¸µÅ©
TitleIndex
ºí·Î±×
°³¿ä
ÃÖÀûÈ
°Ë»ö °ø°£ ÃÖÀûÈ
Open/Closed ¸®½ºÆ® ÃÖÀûÈ
°æ·Î º¸¿Ï
±âŸ ÃÖÀûÈ
¸µÅ©
1 °³¿ä
°¡Àå À¯¸íÇÑ ³ëµå ¹æ½ÄÀÇ ±æÃ£±â ¾Ë°í¸®Áò.
ÀϹÝÀûÀÎ ¿¹Á¦´Â 8 ¹æÇâÀÇ ¿òÁ÷ÀÓÀ» ±âÃÊ·Î ÇÑ °ÍµéÀÌ ´ëºÎºÐÀÌÁö¸¸, »ç½Ç ¹æÇâ°ú´Â º° °ü°è°¡ ¾ø´Ù. ÀÓÀÇÀÇ ³ëµå°¡ À̾îÁ® ÀÖ´Â ´Ù¸¥ ³ëµå¸¦ ãÀ» ¼ö ÀÖ´Â ±¸Á¶(±×·¡ÇÁ!)¸¸ µÇ¾î ÀÖ´Ù¸é, ¾î¶² ÀÚ·á ±¸Á¶¿¡µµ Àû¿ëÇÒ ¼ö ÀÖ´Ù. ÀÌ¿¡ °üÇÑ »çÇ×Àº
SearchSpaceRepresentation
ÆäÀÌÁö¿¡¼ ´Ù·é´Ù.
2 ÃÖÀûÈ
2.1 °Ë»ö °ø°£ ÃÖÀûÈ
ÀÏ´Ü °Ë»öÇÒ ³ëµåµéÀÇ ¼ýÀÚ¸¦ ÁÙÀÌ´Â °ÍÀÌ °¡Àå ¸ÕÀú ÇØ¾ßÇÒ ÀÏÀÌ´Ù. °èÃþÇü °Ë»ö °ø°£À» ¸¸µå´Â °ÍÀÌ ÀÌ ¹üÁÖ¿¡ ¼ÓÇÑ´Ù.
2.2 Open/Closed ¸®½ºÆ® ÃÖÀûÈ
°æ·Î¸¦ °Ë»öÇÏ´Â µ¿¾È, Open ¸®½ºÆ®¿¡¼´Â Æ÷ÇÔ¿©ºÎüũ/»ðÀÔ/»èÁ¦/º£½ºÆ®³ëµå¼±ÅÃÀÌ ÀϾ°í, Closed ¸®½ºÆ®¿¡¼´Â Æ÷ÇÔ¿©ºÎüũ/»ðÀÔ/»èÁ¦°¡ ÀϾÙ.
ÀÓÀÇÀÇ ³ëµå°¡ Open/Closed ¸®½ºÆ®¿¡ µé¾îÀִ°¡ ÆÇ´ÜÇÏ´Â Æ÷ÇÔ ¿©ºÎ üũ ¹®Á¦´Â ³ëµå ÀÚü¿¡´Ù bool º¯¼ö 2°³¸¦ µÒÀ¸·Î¼ °£´ÜÈ÷ ÇØ°áÇÒ ¼ö ÀÖ´Ù. ´Ù¸¸ ÀÌ·¸°Ô ÇÏ¸é ¿©·¯ ½º·¹µå¿¡¼ °°Àº ±×·¡ÇÁ¿¡ ´ëÇØ µ¿½Ã¿¡ ±æÃ£±â¸¦ ¼öÇàÇÏ´Â °ÍÀº ¾î·Á¿öÁø´Ù.
Open ¸®½ºÆ®¿¡¼ º£½ºÆ® ³ëµå¸¦ »Ì¾Æ³»´Â µ¥¿¡´Â ÈüÀ» ÀÌ¿ëÇÑ ¿ì¼± ¼øÀ§ Å¥¸¦ ÀÌ¿ëÇÏ´Â °ÍÀÌ ÁÁ´Ù.
2.3 °æ·Î º¸¿Ï
°Ë»ö °ø°£ÀÌ ±×¸®µå ±â¹ÝÀÎ °æ¿ì, ¿¡ÀÌÀüÆ®ÀÇ ¿òÁ÷ÀÓÀÌ 45µµ ´ÜÀ§·Î Á¦ÇѵȴÙ. Ź Æ®ÀÎ °ø°£¿¡¼, »ç¶÷ ´«À¸·Î º¸±â¿¡´Â Á÷¼±À¸·Î À̵¿ÇÏ´Â °Ô ÀÚ¿¬½º·¯¿ö º¸À̴µ¥, ¿¡ÀÌÀüÆ®´Â ¾µµ¥¾øÀÌ ¹æÇâÀ» ¹Ù²ã°¡¸ç ±¸ºÒ±¸ºÒÇÏ°Ô ¿òÁ÷ÀδÙ. À̸¦ ÇØ°áÇϱâ À§Çؼ´Â Áß°£¿¡ °ÅÄ¡´Â ÇÊ¿ä¾ø´Â ³ëµåµéÀ» ³¯·Á¾ß ÇÑ´Ù.
ÇÊ¿ä¾ø´Â ³ëµå¸¦ ÆÇ´ÜÇÏ´Â °ÍÀº ºñ±³Àû °£´ÜÇÑ ÀÏÀÌ´Ù.
V0, V1, V2·Î ÀÌ·ç¾îÁö´Â °æ·Î°¡ ÀÖ´Ù°í ÇÏÀÚ.
V0 -> V2 »çÀ̸¦ ÀÕ´Â Á÷¼± »óÀ¸·Î ¿¡ÀÌÀüÆ®°¡ ¿òÁ÷ÀÏ ¼ö ÀÖ´ÂÁö üũÇÑ´Ù.
À̵¿ÇÒ ¼ö ÀÖ´Ù¸é V1 ³ëµå¸¦ ÆÐ½º¿¡¼ Á¦°ÅÇϰí, V0, V2, V3¸¦ °Ë»çÇÑ´Ù. Á÷¼±À¸·Î À̵¿ÇÒ ¼ö ¾ø´Ù¸é V1, V2, V3¸¦ °Ë»çÇÑ´Ù.
ÀÌ·± ½ÄÀ¸·Î Àüü ³ëµå¸¦ ÃÖÀûÈÇÏ¸é ±¸ºÒ±¸ºÒÇÑ ¿òÁ÷ÀÓÀ» ÃÖ¼ÒÈÇÒ ¼ö ÀÖ´Ù. "Á÷¼± »óÀ¸·Î ¹Ù·Î À̵¿ÇÒ ¼ö Àִ°¡"¿¡ ´ëÇÑ Ã¼Å©´Â °£´ÜÇÏ°Ô ÇÏÀÚ¸é line of sight ¹®Á¦¶ó°í º¼ ¼ö ÀÖ´Ù. ´Ù¸¸ ¿¡ÀÌÀüÆ®ÀÇ Å©±â°¡ Á¦°¢°¢ÀÎ °æ¿ì¿¡´Â ´Ü¼øÈ÷ line of sight¸¸À¸·Î´Â ¸ðÀÚ¶ó¹Ç·Î Ãß°¡ÀûÀΠüũ°¡ ÇÊ¿äÇÏ´Ù.
³×Æ®¿öÅ© °ÔÀÓ °°Àº °æ¿ì¿¡´Â ¹æÇâÀÌ ¹Ù²ð ¶§¸¶´Ù ÁÖÀ§¿¡ À̸¦ ¾Ë·Á¾ß Çϴµ¥, ¹æÇâÀÌ ¹Ù²ð Àϵµ Àû¾îÁö´Â ºÎ¼ö È¿°ú°¡ ÀÖ´Ù.
2.4 ±âŸ ÃÖÀûÈ
Ÿ°ÙÀÇ À§Ä¡°¡ ¾à°£ º¯°æµÇ¾ú´Ù°í ÇØ¼, ¸Å¹ø °æ·Î¸¦ »õ·Î ãÀ» ÇÊ¿ä´Â ¾ø´Ù. Ÿ°ÙÀÌ ¸¶Áö¸· À§Ä¡¿¡¼ º°·Î ¸Ö¾îÁöÁö ¾ÊÀº °æ¿ì¿¡´Â ¿ø·¡ °æ·Î¸¦ ÅëÇØ ¸¶Áö¸· À§Ä¡±îÁö À̵¿ÇÑ ´ÙÀ½, »õ·Î °æ·Î¸¦ °Ë»öÇØµµ µÈ´Ù. (¹°·Ð ¼ø°£¼ø°£ÀÇ Å¸À̹ÖÀÌ Áß¿äÇÑ °ÔÀÓÀÇ ¿¡ÀÌÀüÆ®, ¿¹¸¦ µé¾î FPS °ÔÀÓÀÇ ¿¡ÀÌÀüÆ® °°Àº °æ¿ì¿¡´Â ¹«¸®ÀÏ ¼öµµ ÀÖ´Ù.)
¸ñÇ¥ ÁöÁ¡±îÁö °¡´Â ±æÀ» ¹Ýµå½Ã ã¾Æ¾ß ÇÒ Çʿ䰡 ¾øÀ» ¼öµµ ÀÖ´Ù. ¾î´À Á¤µµ ÀÌ»óÀÇ ³ëµå°¡ ¿ÀÇ ¸®½ºÆ®¿¡ µé¾î°¬´Ù. ½ÃÀÛ ÁöÁ¡¿¡¼ ¾î´À Á¤µµ±îÁö ¸Ö¾îÁ³´Ù. ±æÃ£±â¸¦ ½ÃÀÛÇÑ ÈÄ ¾ó¸¶¸¸ÅÀÇ ½Ã°£ÀÌ Áö³µ´Ù. ÀÌ·± Á¶°ÇµéÀ» ÀÌ¿ëÇØ ±×³É ·çÇÁ¿¡¼ ºüÁ®³ª¿Í ÇöÀç±îÁö ±¸¼ºÇÑ ÆÐ½º¸¦ ¹ÝȯÇÏ´Â ¹æ¹ýµµ ÀÖ´Ù. ¸ñÇ¥ ÁöÁ¡±îÁö ¹Ýµå½Ã ã¾Æ°£´Ù´Â °ÍÀº º¸ÀåÇÏ±â ¾î·ÆÁö¸¸, °Ë»ö °ø°£ÀÌ ¾öû º¹ÀâÇÏÁö ¾ÊÀº °æ¿ì, ¾î´À Á¤µµ ¸Â¾Æ¶³¾îÁø´Ù.
±æÃ£±â¿¡ ºÎ¿©ÇÒ CPU ½Ã°£ÀÌ ¸ðÀÚ¶õ °æ¿ì¿¡´Â ½ÃºÐÇÒ ¹æ½ÄÀÇ ¾Ë°í¸®Áòµµ »ý°¢ÇØ º¼ ¼ö ÀÖ´Ù. ´Ù¸¸ ÀÌ·¸°Ô µÇ¸é ¿¡ÀÌÀüÆ®ÀÇ ¿òÁ÷ÀÓ Ã³¸®°¡ ºñµ¿±â ¹æ½Ä°ú ºñ½ÁÇØÁö±â ¶§¹®¿¡ ÄÚµùÇÏ´Â °Ô Á» ±ÍÂú¾ÆÁø´Ù. ¶ÇÇÑ Çѹø¿¡ ¸ðµç °æ·Î¸¦ ã´Â °ÍÀÌ ¾Æ´Ï±â ¶§¹®¿¡ óÀ½¿¡´Â À߸øµÈ ±æ·Î °¡´Ù°¡, ½Ã°£ÀÌ Á» Áö³ª¼¾ß Á¦´ë·Î µÈ °æ·Î·Î ¿òÁ÷ÀÌ´Â Çö»óÀÌ ¹ß»ýÇÒ ¼öµµ ÀÖ´Ù. ´ë½Å ¹ÝÀÀ¼ºÀº È®½ÇÈ÷ Áõ°¡ÇÑ´Ù. RTS·ùÀÇ °ÔÀÓ¿¡¼ ÀÌ·± ¹æ½ÄÀ» ¸¹ÀÌ ¼±ÅÃÇÏ´Â °É·Î ¾Ë°í ÀÖ´Ù.
3 ¸µÅ©
Amit¡¯s Game Programming Information > Shortest Paths
Micro Pather
A* Pathfinding for Beginners
Two-Tiered A* Pathfinding
Using Binary Heaps in A* Pathfinding
Heuristics and A* Pathfinding
A* algorithm implementation in C#
Gamasutra > Pawn Captures Wyvern: How Computer Chess Can Improve Your Pathfinding
IDA* (Iterative Deepening A*) ¾Ë°í¸®Áò¿¡ ´ëÇÑ ¼Ò°³.
Àç±Í È£ÃâÇÏ¸é ½ºÅà ¿À¹öÇ÷οì ÀϾÁö ¾Ê³ª? Transition TableÀº ¶Ç ¾î¶»°Ô ±¸¼ºÇؾßÇϳª? ³ªÁß¿¡ ´Ù½Ã Çѹø ÀоÀÚ.
see also
PathFinding
CategoryAlgorithm
,
CategoryAiProgramming
FindPage
by browsing, title search
, text search
or an index
Or try one of these actions:
AttachFile
,
DeletePage
,
LikePages
,
LocalSiteMap
,
RenamePage
,
SpellCheck
SeriousMoin
v1 (
koMoinMoin
1.0a4 Modified)