Waiting for presentation
* * *
--:--:--
조금 이른 주제지만...
추석 전 쯤에 이 세미나를 하면 좋겠다고 생각했습니다 :)
민속놀이
민속놀이라고 하면 무엇이 생각나시나요?
윷놀이
40대 이상
화투
30대 이상
스타크래프트
20대 이상
우리가 어떤 민족입니까?
- Starcraft Korea Server Introduction
Choi Subong
11 Million
Best-selling strategy videogame for PC
- Guiness World Records
Masterpiece of RTS
-
7 GOTY
GameSpot | Computer Gaming World | PC PowerPlay
PC Gamer | Game Domain | AIAS | Game Informer
- 93% GameRankings
- 88 Metacritic
- 9.5 IGN
- 92% PC Gamer
- 9.1 GameSpot
- 9.0 GamePro
100,000
over spectators
2005 Starcraft Professional League
Gwangalli, South Korea
Unbalance Game?
- 36 Terran Champion
- 29 Zerg Champion
- 16 Protoss Champion
- 60 Terran Finalist
- 62 Zerg Finalist
- 40 Protoss Finalist
The development team was able to work around some of the other path-finding problems and just plain ignore the rest, though the Protoss Dragoon in particular ended up with a bad reputation because, as the largest ground-unit, it frequently failed to path well.
Why are protoss stupid?
Starcraft's Pathfinding Algorithm
How to pathfinding in Computer
- 1. Represent terrain as data structure.
- 2. Pathfinding
- 3. Optimizing
So, How to find a way?
- DFS Depth First Search
- BFS Breadth First Search
- Dijkstra Search Shortest path in Graph
- A* Heuristics Search
DFS
Left(Right)-Hand Method
What if the maze is transformed?
What if there is cycle(回) in the maze?
It can find just path, not shortest.
BFS
Flood fill
Like a flood, finding shortest path.
Too many COST.
BFS is not considering weighted path.
Dijkstra
Considering weighted path
Dijkstra algorithm can considering weighted path.
pure Dijkstra algorithm still HIGH COST.
Dijkstra can reduce execute time with Priority Queue.
A*
Heuristics Search
What if you could predict the lower bound of the remaining distance?
Explore nodes with high probability(Priority) of correct answers.
Priority(current) = Cost(start,current) + Estimate(current,end)
Cons of A*
A* was too heavy in 1998
A* algorithm is not low cost.
Exponential cost increases with size N.
StarCraft has a maximum map size of 10242.
Let's think.
How to go to Korea Univ?
Let's think.
How to go to Korea Univ?
Search approximate routes based on well-known point(e.g., subway stations, bus stop).
Move from current point to well-known point.
Obstacles encountered during move are avoid as soon. Obstacles are not consider before moving.
in Starcraft
Divide and conquer
Reduce N using the 2 step pathfinding algorithm.
They called the method the Pathfinding regions.low cost A* in same region
Search next regions by Dijkstra, and go regions by A*.
Detail Rule
3 Grid or less
Find optimal path by A*
Over 3 grid
Follow Pathfinding regions.
When they meet an object
if object is stop:
Avoid object by A* algorithm
else:
Waiting for object to go away from path
not Perfect
but BEST
It just check average size collision box
Some unitDragoon, Ultralisk can't move narrow area.
but navigation system forced one way.
Sometimes they unnaturally move
It stands out from the boundaries of the regions.
When two moving objects collide, the path becomes very strange.
Pathfinding regions NEVER update
when Pathfinding region is stuck, it can't find another way.
Why Terran more
efficient than others
Starcraft II
in Game Engine
-
UnrealEngine
-
Unity
Let's think.
How can I find neighborhood?
Let's think.
How can I find neighborhood?
Over 100,000,000 points
Quad Tree
Region Management
but, in real world...
Behind Story
Patrick Wyatt
Can you make it with using legacy code, right?
Blizzard management plans to make Starcraft using the Warcraft engine in a year.
Developers are exhausted from Continuous Crunch Mode.
Unreasonable schedule for money.
Q4 1994 – Warcraft I
Q4 1995 – Warcraft II
Q4 1996 – planned ship date for StarCraft
Orcs in space
StarCraft as it appeared in June 1996 at the Electronic Entertainment Expo.
The development team felt ashamed to see other entries.
At the same time, in Diablo team...
Reboot Starcraft
In the gaming world you’re only ever as good as your last game.
Starcraft needed to go far beyond what we’d done previously, and that required taking risks.
build a strategy of Blizzard; Not releasing games until they were ready.
In the gaming world you’re only ever as good as your last game.
Starcraft needed to go far beyond what we’d done previously, and that required taking risks.
build a strategy of Blizzard; Not releasing games until they were ready.
Should we try this too?
Good design of isometric like Diablo.
But, Warcraft II engine is base rectangle, not isometric
(design for top-down view, not quarter view).
Come too far...
Fix the Warcraft II engine, fix it, fix it...
The root of all evil; Quarter view, but rectangle map logic?
Cut the squares into smaller pieces!
An idea ahead of its time.
Save & load
Replay
Voice chat
Dirty code, frequent hack...
but it is work.
Wrong architecture, and many change Requirement specification
Non-continuous bug fix like first aid.
But users liked these bugs called glitches.
One always exceeds
one's expectations.
Conclusion
We know pathfinding algorithm
Starcraft pathfinding algorithm is too stupid and slow.
But, in 1998, that algorithm is revolution.
Why did Starcraft become a masterpiece?
It's late, but the right decision.
The enthusiasm and commitment of the staff's passion and commitment.
Creative Attempts.
Trick or hack; Not afraid of the dirty code.
Now we know starcraft's behind stroy.
We should be careful not to repeat the same mistake.
Reference
Hagelbäck, Johan. "Potential-field based navigation in starcraft." 2012 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, 2012.
Halldórsson, Kári. Using Map Decomposition to Improve Pathfinding. Diss. 2015.
Cui, Xiao, and Hao Shi. "A*-based pathfinding in modern computer games." International Journal of Computer Science and Network Security 11.1 (2011): 125-130.
Sturtevant, Nathan R. "Benchmarks for grid-based pathfinding." IEEE Transactions on Computational Intelligence and AI in Games 4.2 (2012): 144-148.
Wikipeida "Starcraft"
Patrick Wyatt. "Tough times on the road to Starcraft". 2012.
Patrick Wyatt. "The StarCraft path-finding hack". 2013.
Blizzard "The Brood War API". Github
Mark Terrano , Paul Bettner. "1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond". Gamasutra. 2001
Thank you!
any question?