krogenth / additionalpylons Goto Github PK
View Code? Open in Web Editor NEWA StarCraft Broodwar AI written in C++20
License: MIT License
A StarCraft Broodwar AI written in C++20
License: MIT License
Currently, we only specify a series of things to build at the very beginning of a match, and nothing else. Now we will need to handle non-starting build orders, to continue building and eventually (hopefully) win the match.
This task can be broken into 2 separate PRs:
In order for this to work, you will need to fulfill several things:
0.0
or FLOAT_MAX
, we likely have none)FLOAT_MAX
for the ratio of gas:mineral workers)Due to the limited time of this project, and the requirement to compete within the ELO ladders, we'll need to limit the scope of what is worked on. To reach that goal, we can use the community libraries for handling map analysis and building placement.
Specifically, we can include:
These should be included as submodules within the repository, and added to the projects, including adding basic handling of any onStart
, onFrame
, onUnitCreate
, and onUnitDestroy
functionality they include.
With the Resources added to the Map in #16, we will need to generate a listing of all possible Bases in the Map. A Base should essentially be a BWAPI::TilePosition
that is optimal for a Hatchery to be placed in proximity to any Minerals and Geysers. We can gather the starting locations through BWAPI::Game::getStartLocations
, however this does not include and Naturals or other expansions. We will need to calculate these Base locations based on the Mineral and Geyser positions.
The Map should now be able to:
Currently, our BuildingWrapper
can only handle morphing itself into a new building. Some buildings are capable of researching upgrades for our units(upgraded movement, attack rate, attack range). Upgrade are completely independent of BWAPI::UnitTypes
, classified as BWAPI::UpgradeTypes
.
As such, we will need multiple things:
BWAPI::UnitType
BuildingWrapper
logic to retrieve an upgrade and begin upgradingUnitWrapper
isBusy()
changes required to pause a building from attempting to create or upgrade anything elseWe'll need to analyze the state of the game, and attempt to estimate the best possible course to win. For now, we will only choose an initial Build Order based on Map size from #4 to initialize a starting building queue. The Strategist should check what the first order is on each frame to see if the requirements(and resources) are available to make the order. Like the Map in #2, this will be a Singleton. For now, we will use queues to store Build Orders for Units to ask for.
The Strategist should contain:
Zerg_Larva
, Zerg_Drone
, and Zerg_Hatchery
Build Order queuesRemember, there may be nothing in the Build Order queue for the Unit asking, it's recommended to use std::optional
for this.
We have so far implemented handling mineral collection to a slight degree, however we will also need to handle the secondary resources: gas. Gas is a special resource, requiring an BWAPI::UnitTypes::Extractor
to be built on top of a Vespene Gas Geyser. The majority of starting bases will have at least one such geyser.
In order to properly implement this, there will need to be multiple considerations:
For this to be properly implemented, there may be need to use BWEM, and possibly a wrapper class for the resources BWEM gives in order to associate units to that resource(possibly keeping a count of workers in the resource class, while a worker holds a pointer to the resource it is mining).
The last Strategist play decision, attack, is as it sounds: order our units to go on the offensive, attacking enemy units as they can. There are some major caveats to this however:
This decision is completely situation dependent, based on the unit in question, what units the enemy has, what enemy units are near by, what player units are near by, etc. All of this factors in to what a unit should do in some way.
This task is to implement any such logic for ALL Army unit wrappers.
For more complicated Building Placement, we may want to consider the idea of marking parts of the Map as an Area. An Area is not required to contain a Base location/resources.
A possibility is to mark an Area based on the buildability/walkability and altitude of the tile(s) it will/can contain.
We'll want units to handle orders in potentially special ways, therefore we will need wrapper classes for our Player Units to better implement such requirements.
For now, this class should:
BWAPI::TilePosition
queue they are need move to reach the final target destinationfunctionality:
In every game, we'll only know that the enemy is an Unknown
race at the start. As such, we will need a way to switch what we are attempting to do based on newly acquired information through scouting. If an enemy unit is seen, we will need to call to the Strategist to retrieve the Player's currently existing units and buildings, and update the starting build order queue to only hold BWAPI::UnitType
for what we do not have within the newly selected initializer_list
.
In order to facilitate this functionality, you will also need to add to the Player
class:
We'll want to keep track of what resources are on the game map and where they are located. For Map initialization, we will want to retrieve and store all Minerals and Geysers in the match. To do this, we can use BWAPI::Game::getStaticMinerals
and BWAPI::Game::getStaticGeysers
to retrieve the full listing of resources.
For Mineral patches that we cannot see, we may not get an event trigger of that Mineral patch being mined out. Though it should be a very low probability that we take a base another player has mined out or used in general.
For Zerg buildings, orders are fairly straight forward: morph or make upgrades, so a building's handling of an order will only contain the BWAPI::UnitType
to make without a BWAPI::TilePosition
or any positional checking. Just like the order handling in #31, orders can be retrieved from the Strategist's getUnitOrder(BWAPI::UnitType type)
method.
Similar to Workers, for Zerg, there are larva, which will morph into other units. We will need to keep track of these larva and issue build orders to them as needed. Larva should only be busy when they are morphing, and can only be morphed once. Larva will do nothing except eventually morphing into a different unit.
Overlords are the supply providers for Zerg, and as such are vital to ensure we can continue producing additional units. Overlords are capable of moving, and can be used for early game scouting along side a drone. For now, Overlords should try to stay in the safest position possible, in the back of our Base.
Overlords can have only one job, depending on if the Strategist wants them to:
During the early and possibly late game, we may need to handle searching for the enemy to direct our army towards. Once a starting location has been scouted, it should not be checked again until all possible starting locations have been scouted.
In order to appropriately handle early and late game, BWEM/BWEB may be required in some of the logic handling.
notes:
OverlordWrapper
's onFrame
to test this functionalityWe'll need to have some form of chokepoint detection in order to in more optimal positions to defend/place defenses. BWAPI does give us a list of regions through BWAPI::Broodwar->getAllRegions()
, where region->getDefensePriority() == 2
is what Broodwar auto-determined to be a chokepoint area. Unfortunately, these chokepoints contain many false-positives(including mineral groups, walls, etc.), so attempting to use the BWAPI::RegionInterface
to grab all chokepoints will still require a large amount of calcuating.
Chokepoints should be generated upon Map initialization.
When defending, we will want to completely maximize our chances of success against the enemy. To better facilitate this, we will want to generate a concave formation of melee units on a chokepoint, to maximize the ratio of units engaged in the fight in our favor.
In order to generate a concave formation at any chokepoint, we will need:
BWEB::Map::perpendicularLine
This is just a general idea of how this should work. Further research should be done to refine how this should appropriately work.
We'll want to keep a record of all game map tiles in local memory for efficiency and better possible calculations. Each tile will be equivalent to a BWAPI::TilePosition
point.
Each tile should at least keep track of:
The tiles walkability, buildability, and last frame seen values should have getters and setters.
We'll need a way to decide the best possible place to build buildings. For now, this should be a very basic handling, based on the starting location of the Player.
Since Zerg requires creep to build buildings, we will need to verify that creep exists on the tile and that the tile is buildable before returning the tile.
Using the BWAPI::Unit wrapper interface from #7, we'll want to create a custom BWAPI::Unit wrapper specifically for workers. For now, workers can go to the nearest minerals to the starting location.
Workers will have several potential jobs to perform:
We may eventually implement some form of attacking as well, primarily for the event where an enemy has rushed us.
We'll want to keep a rough idea of opening plays we can/should make depending on knowledge we have at the time. For now, we will only consider the map size.
As such, we'll want 3 different types of opening Build Orders based on map size:
All Build Orders should use an std::initializer_list
to define the list of std::pair
's of BWAPI::Unit
and int
(supply used) to define when a build order should occur.
Broodwar counts the majority of units as 2 supply instead of 1, except zerglings, they are counted as 1 supply.
A good resource for various Zerg build orders can be found here: https://liquipedia.net/starcraft/Category:Zerg_Build_Orders
We'll need to handle calculating a relatively optimal path to some point on the Map from #2. Recommended researching various pathfinding algorithms, but A-Star may be best to implement at minimum. There should be a way to specify if walkability is a requirement for the path calculation or not).
Some resources that may help with regards to A-Star:
https://theory.stanford.edu/~amitp/GameProgramming/
https://github.com/daancode/a-star
https://github.com/Rikora/A-star
The returned value should be a queue of BWAPI::TilePosition
's.
In order to better determine what our Army and scouting units should do, we will need the Strategist to specify what type of play we should be doing. These plays will include:
While the Strategist itself will not directly command units, these decisions will help facilitate the unit's individual decision making.
At the start of a game, the opening decision should be to scout, in an attempt to discover where the enemy's main base is. But as the game progresses, we will want to potentially adjust what the general decision is.
We'll want to keep track of what each player owns. We will be considering every match to be a 1v1, regardless of how many players are actually participating. As such, there should only be two global instances: a player(us) and enemy(not us). Each player should be capable of resetting between matches, and should be called in the bot Module's onStart()
or onEnd()
. Any neutral units do not fall under either category of player.
Each player should keep track of:
The Player class should implement:
As we continue to implement more and more complex logic for our unit wrappers, we will want to have ways to more easily discern what is occurring and when. All debugging information should be limited to the Debug
configuration. As such, we will want at least the following information:
onFrame
method takesonFrame
method(not their displayInfo
method)displayInfo
methodfor all timing calculations, you can generally follow this: https://stackoverflow.com/a/37984848
Army units, like NonArmy units, come in a variety of types. The Army types for now will include:
For now, since the Strategist does not handle combat simulation nor scouting, the Army Units can simply grab the main or natural's choke location, and move there to defend.
Like Workers and Army units, Buildings can have their own individual logic to better perform their tasks. Same as the WorkerWrapper #11 and ArmyWrapper #14, this will also inherit from the UnitWrapper #7. For Zerg, no buildings are capable of moving, but are capable of producing upgrades and potentially morphing.
As such, we will need to implement:
For now, this wrapper will do nothing, but the isBusy
method should be implemented to the best we can manage at the moment. The displayInfo
should only display what state the building is currently in(this can be determined via the isBusy
method.
For Zerg, morphing is the basis of progress. When the Module onUnitMorph
is triggered, we will only know what the new version of the unit is. The onUnitMorph
event is triggered twice: when the unit initially morphs, and when the unit finally ends morphing. For the Player's onUnitMorph
, the original unit should be removed from all maps, and the new unit inserted into whatever maps it belongs to(the onUnitCreate
method can be leveraged for this).
To make better strategic calls, we will want to keep track of what each player's race is, therefore, we should attempt to keep track of each player's race inside the Player class object.
The Player class should hold:
The Player class should implement:
BWAPI::Race
if the stored BWAPI::Race
is BWAPI::Races::Unknown
once a unit from that player is discoveredBWAPI::Race
upon initializationBWAPI::Race
For any bots that choose to play a Random
race, we will not know what race they are playing until a unit of theirs is seen.
Some opening plays are difficult to predict/counter. While Zergling rushes may work 50/50, it may not always be the best possible play to open with every match. As such, we'll want to consider opening plays that at least tend to work well against specific races, while taking into account the size of the map. Since the map size may potentially play a part in determining how we should proceed. For example, a small map would favor a Zergling rush, but a larger map would favor a Hydralisk/Mutalisk play.
These lists should behave the same way as the Build Orders lists in #4, specifying the BWAPI::UnitType
and the amount of supply used to trigger the build.
We'll need a way to determine if it is possible to win an engage against the enemy. Handling issues like altitude difference, distance, etc. for every unit will be too computationally extreme. For now at least, we can based everything off of all Army units each player has, and consider the distance from the average of both groups. The general idea of StarCraft's unit balancing is generally a rock-paper-scissors match. With this, we can roughly calculate based on what counters what for each race, to determine which side SHOULD win in a fight.
We will want 3 main Combat engines, one against each race to help split up the code base into more manageable pieces.
The Strategist should call whatever Combat engine is required(if the enemy's race has been determined) to determine what the play should be.
With the way StarCraft maps are typically laid out, it would be beneficial to mark sections of the Map as an "Area", and specify what is located within that area, or near it(Chokepoints, other Areas, etc.). This requires a lot of graph theory/mathematics, specifically Voronoi Diagrams and the use of Manhattan Distance calculation. Additionally, having some form of rough bounding box, or boxes for the Area may help. Some consideration of reading what BWEM does may prove beneficial.
If possible, we will want to specify what is within an Area on the Map, including:
The BWAPI UnitInterface's getDistance
function completely ignores walkability and returns the distance in pixels, both can be problematic for determining what Unit(s) we should target in combat. We'll need to compare rough walking/Flying distances between Units to determine which Unit should be focused. With #5 we can calculate the distance between by counting the number of tiles required to reach the destination.
With the Strategist play decisions from #43, we can now successfully handle giving orders to our units. For this task we will only consider the defending
decision. When defending, we should place our units in the most optimal of locations possible when defending, this is typically:
For Zerg, our unit range is rather low, so if a chokepoint expands past a Hydralisk's range from the high ground, defending the chokepoint itself should take precedence. Chokepoints can be retrieved from BWEM.
We'll want to keep a record of the entire map state. This map will be a singleton, only one instance of a Map should ever exist at any time. This task only deals with regards to map initialization and tiling, no units/resources. The Map should be capable of resetting between matches, and should be called in the bot Module's onStart()
or onEnd()
.
This includes:
BWAPI::TilePosition
functionality:
For more information on the Singleton design pattern: https://stackoverflow.com/questions/1008019/c-singleton-design-pattern
As a game progresses, we will need to expand our claim of territory in the map. While the Strategist does provide a BWAPI::UnitTypes::Zerg_Hatchery
for workers to morph into, currently workers will only pick the nearest open BWEB
block the hatchery fits in. We will need to add logic to both the worker and strategist to handle if we should take an expansion, and which expansion we should take. Typically, the first expansion will always be the "natural", which typically holds more minerals, a geyser, and is typically the closest base by ground distance. All expansions after the natural expansion can be arbitrarily determined by the strategist based on some form of criteria(is it possible to secure, is the enemy there or near by, can we give enough supplies(workers, defense, etc.) to an expansion, really whatever you can think of).
With this, the worker building a hatchery should request if this is meant to be an expansion, and if so, query what expansion is best.
In order for the Strategist's combat engines to better handle calculations, we will need ways to retrieve listings of units associated with a Player.
There will need to be functionality for:
BWAPI::UnitType
units associated with a PlayerWith the Strategist created in #12, we now are able to issue orders to units. All unit wrappers can call upon the Strategist's getUnitOrder(BWAPI::UnitType type)
method to retrieve the next possible build to perform. A Worker should only be asking for a build order when they are not busy. Any build that fails should not be discarded, but retried(possibly double checking that a building does not already exist in that location).
To retrieve a building location, you can use BWEB
to retrieve a location. BWEB
's functions for onUnitDiscover
, onUnitMorph
, etc. should also be added to Module to properly keep track of what is where in the map as well.
Army units come in a wide variety, from melee to ranged to air and even burrowed. Each "type" of unit can better use certain tactics over others(hit and run vs grouping). As such, it would be beneficial to handle different units in different ways, using different classes for their specific use case(s). This class will act as the template for these units, building off the Unit wrapper from #7.
This interface should include:
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.