Hey folks,
first excuse me for my bad english..;)
I want to introduce you an idea of using ant-based algorithm to solve a problem or give you an idea for a new game-logic for a construct2 based game.
I?ve done a few researches during my computer science study about ant-based algoritms for mobile area networks (MANET).
Whats the idea?
Well, this kind of algorithm (called swarm-intelligence) are used to solve combinatorial problems in an easy way. Specialy to find shortest path between nodes in a graph.
But! you can also use it to solve other problems, where you have to find a optimally solutions when you have many options to choose.
This sounds a little abstract? It is. So a little example:
Think about a salesmen, who has to visit a few cities, but he has to use/find the shortest path between them. Lets call the cities a,b and c. The cities are connected with a street and it is known the "weight" (the distance) of that streets.
This task is easy: We?ve got the possibilities a^b, a^c and c^b, compare the distance between them and we will find the shortest path in no time.
But with every additional city, that task would be exponentially bigger to solve. With 10 cities, we have to compare 3.6 billion possibilities!
Why ants?
So why ants? Ants have a easy solution to find food and bring that food back to there base.
- First, they move randomly around
- If one ant find some food, it takes the food and move home to base. While the ant is moving, it places "pheromones" to the ground so other can use that track to find the food as well.
- In the meantime, other ants find the food on other ways, put pheromones on the ground and moving back to base.
Right, at this point imagine the ants using different tracks to the food source and different tracks back to the base.
To find the shortest way, there are two conditions:
1. The ants using always the track with the highest pheromone level
2. After some time, the pheromones evaporates.
What happens?
The ants needs more time to move along the detours towards the food source. So on this tracks, the pheromones evaportes quicker then other shorter path (keep in mind, the ant droppes always pheromones on the way back to the base), while on the shortest path the pheromon level increases more and more. After a while, only the the shortest path is used, because its the only track with pheromones on it (and with the highest concentration).
That?s it. The shortest path is found without heavily calculation.
For more infos: Wikipedia
But how to use in construct2?
Ok first i have to admit, you could use the pathfinding plugin in almost every scenario. But in my experience, with hundreds or thousands enemies...well it has a realy bad performance. So in this case, you can think about using such an algorithm.
If you want to build a ant-simulation, you have to use this algorithm :)
My prototype:
Thats what i tried. But im not that good in construct2. So feel free to use my approach and modify it.
My first idea was to build a grid (background, invisible). The tiles got some heavy "obstacle-weights" (pathfinding-plugin).
- The Ant-Agents starts at a base and randomly walk around the scene.
- When they hit the food-source, they use the pathfinding-tool to walk back to the base.
- Every time they hit a grid-tile, they remove it.
- Other agents ..should use the same way back, because the way is clean of obstalces.
- After some time, the grids re-appear.
So i used the algorithm the other way around.
You can implement this algorithm to build a KI for a chess game, or you can just use it let the KI move around whatever you want.
Alright, i hope you get inspired ;) See ya!