Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
July 20, 2019
arrowPress Releases







If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 

Implementing SEO in Video Games

by Ashley Kreuer on 06/24/19 10:40:00 am

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

 

So we all know Google and other search engines use a variety of optimization techniques. How does that apply to video games? Well the classic example is the shortest path problem. You want your AI whether it be enemies or NPC’s to take the shortest path to the player or some other goal. The way to accomplish that dynamically is to use a search algorithm.

The first thing you need to know when implementing this sort of algorithm is how to set up the problem. There are essentially 3 variations you need to worry about single-source shortest path problemsingle-destination shortest path problem, and all-pairs shortest path problem. The first one is essentially you have a starting location and you are trying to find a route to every other place on the map. The second is basically the opposite of the first. You are trying to find the shortest path from all possible starting locations to a single end point. The last one is both combined. You are trying to find the shortest rout between all possible starting and ending locations.

Now you have a variety of options for algorithms Dijkstra’s, Bellman-Ford, A*, as well as a few others that I’m not going to get into. The first two are excellent algorithms but the benefit of using the A* Search Algorithm in video games is that it adjusts for a heuristic(basically a rule or sort of hunch of which direction to go). Now this is where you can really let your creativity shine when it comes to AI characters. You can make some of them move more optimally. You can make them become stunned or disoriented and move less optimally. You can even add in another goal or end condition. Now traditionally the heuristics are used to speed up the algorithm. You can use it for that perhaps routing over terrain that lets the AI move faster and is more likely to connect two points for example roads. The thing to remember though when you are implementing them is that it is up to you how you want use and/or modify the search algorithms. This can be a bit of a scary thing if it isn’t something you’ve done before. Personally it is something I love. I really enjoy writing custom algorithms for problems. I once got very frustrated at a hashing library in the middle of the night and wrote my own single direction hashing algorithm but that is a story for another time.

Suppose you are wanting to use A* and you want to use the heuristic to actually optimize it. There are so many different heuristics you could use customized to your unique implementation. For example maybe because of the way your maps are designed there is a set max minimum distance between every two points say 9 squares, everything is normally within 9 squares of everything else. Well now you can use the heuristic to favor that search range. Maybe you know the direction the goal is in so you make your heuristic to favor paths that go in that direction. Now the problem with this is that if there is a problem with your heuristic it can throw off the entire algorithm.

Heuristics are not the only way to optimize search algorithms. You can also use a technique called pruning. Which like pruning a plant or tree refers to cutting away branches or options that you already know won’t lead to your desired outcome. One example of it is Alpha-beta pruning which is an algorithm that seeks to limit the number of nodes searched by the Mini-Maxi algorithm. It is used for games against an opponent.

Just because an algorithm was designed for a specific purpose doesn’t mean you can’t modify it to suit your specific needs. No one is judging you on how correct your implementation of a specific algorithm is. When considering how you can optimize your search algorithms you have a lot of options from setting up the problem in different formats, using different algorithms, heuristics, and pruning. Search Engines don’t release their algorithms but that doesn’t mean you can’t use some of the same techniques they do to improve your game.


Related Jobs

DMG Entertainment
DMG Entertainment — Beverly Hills, California, United States
[07.19.19]

Game Engineer
Giant Army
Giant Army — Remote, Washington, United States
[07.18.19]

Graphics Developer for Universe Sandbox
Hi-Rez Studios
Hi-Rez Studios — Alpharetta, Georgia, United States
[07.18.19]

Senior Technical Artist
Hi-Rez Studios
Hi-Rez Studios — Alpharetta, Georgia, United States
[07.18.19]

Unannounced Project - Gameplay Programmer





Loading Comments

loader image