Home
/
Blog
/
Hiring Tools
/
Creating your first 2D game with A* Algorithm

Creating your first 2D game with A* Algorithm

Author
Arpit Mishra
Calendar Icon
October 6, 2016
Timer Icon
6 min read
Share

Moving from point A to point B is the prime requirement for many games—whether it is a strategic tactic-based RPG (role-playing game) like Warcraft III or one that’s as simple as Snakes and Ladders. The source-to-destination navigation sometimes requires more intelligence from your character than you believe, it needs to find the path with ease. You can’t have your characters walking through a wall or bumping into a car while playing, can you?

This is where pathfinding algorithms are used. Pathfinding is the basic building block for most games. Players have to reach a destination by moving around blocks, cars, rivers, and prisons. The algorithm ensures that the character not only avoids the obstacles but also gets to the destination by using the shortest path.

Games like Warcraft III use the A* pathfinding algorithm, where the protagonist is not only expected to reach his destination by the shortest path, but also move around the castles, not get in through the huts, dungeon, or walk through a dragon on its way.

A* algorithm (Pronounced A-star algorithm)

The A* algorithm is the fastest graph search algorithm that finds the path that costs the least from source node to goal node. (A node can be hexagon, square or circle, etc.)

In the gaming world, a node graph is a map of your gaming world, and the path that costs the least is the shortest path; A* traverses a node graph and finds the path that costs the least.

A* algorithm has properties of both Dijkstra and Best-first search. Unlike DFS and BFS, the A* algorithm selects the node which looks most promising instead of guessing the next node.

The cost function

The cost of node F is calculated as:

F = G + H

  • G is the cost that is required to reach a particular node from the source node.
  • H often termed the Heuristic Value. It is the estimated cost from one square on the grid to the other square, which is the goal on the grid. H being heuristic, can never be perfect and is usually based on assumptions.

Here we implemented the Euclidean distance for the cost function. The Manhattan and the Chebyshev functions are also shown in case required.

def estimate(self, xDest, yDest):
    """
    Estimation function for the remaining distance to the goal.
    """
    dx = xDest - self.x_position
    dy = yDest - self.y_position
    # Euclidian Distance
    d = math.sqrt(dx ** 2 + dy ** 2)
    # Manhattan distance: d = abs(xd) + abs(yd)
    # Chebyshev distance: d = max(abs(xd), abs(yd))
    return d

Let’s look at the following example:

Traversing A* algorithm

Assume that the graph or table above is a game grid where our protagonist needs to move from the source node of the grid to the goal node.

class Node:
    """
    for handling the individual nodes or spaces in the given map
    """

    def __init__(self, coordinates, distance, priority, possible_directions):
        if isinstance(coordinates, Shift):
            self.x_position = coordinates.change_in_x
            self.y_position = coordinates.change_in_y
        elif isinstance(coordinates, Node):
            self.x_position = coordinates.x_position
            self.y_position = coordinates.y_position
        else:
            self.x_position = coordinates[0]
            self.y_position = coordinates[1]
        self.distance = distance
        self.priority = priority
        self.possible_directions = possible_directions

    def __lt__(self, other):
        """
        comparison method for priority queue
        """
        return self.priority < other.priority

    def estimate(self, xDest, yDest):
        dx = xDest - self.x_position
        dy = yDest - self.y_position
        d = math.sqrt(dx ** 2 + dy ** 2)
        return d

    def updatePriority(self, xDest, yDest):
        self.priority = self.distance + self.estimate(xDest, yDest) * 10

    def nextMove(self, d):
        if self.possible_directions == 8 and d % 2 != 0:
            self.distance += 14
        else:
            self.distance += 10

Let’s consider that every block to the left, right, top, and bottom of the selected (parent) node is at a distance of 1 unit. That means that each block is at a diagonal distance of √2, which is equal to 1.4.

To make things easier, multiply each value by 10, thereby converting the distance to 10 and 14 for adjacent and diagonal nodes, respectively.

Let’s make 2 lists of open and closed nodes. Any node that is selected for the path is moved to the closed node list. Any node that is not selected is considered to be an open node.

How to traverse in A* algorithm

Assume that our protagonist is at the location source. Every block surrounding the location source has a certain F cost, which is obtained by summing G and H.

For example, a block that is diagonally opposite to the source and marked in red would have a G value of 14, an H value of 10, and an F value of 52. You can compute the values for all other blocks similarly.

After we have the cost of all the blocks, select the block which has the lowest cost. In this case, F=52 and mark it as closed.

def a_chosen_direction(x, possible_directions):
    return (x + possible_directions // 2) % possible_directions


def generate_path(possible_directions, dir_map, dx, dy, xA, yA, x, y):
    path = ""
    while not (x == xA and y == yA):
        j = dir_map[y][x]
        c = str(a_chosen_direction(j, possible_directions))
        path = c + path
        x += dx[j]
        y += dy[j]
    return path

Repeat the entire process with all the open nodes and select the block with the lowest F value as you head towards your goal.

Once you reach the goal, the path traversed is the lowest possible path for a given matrix.

How A* algorithm works

Assume that, in a game, the section in black is the area which cannot be traversed by the player.

def collision_with_obstacle(x_y_shift, the_map, closed_nodes_map):
    return any((
        the_map[x_y_shift.change_in_y][x_y_shift.change_in_x] == 1,
        closed_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] == 1
    ))

Select the Source node and calculate the F cost of all its surrounding nodes. Now select the node with the smallest value, which in this case is 48. Then repeat the process.

What if two nodes have the same values, like F=48? In such cases, select any one of them and proceed.

Summary of A* Algorithm
  1. Select the starting point and put it in the open list.
  2. Find the F cost to the current node.
  3. Mark it in the closed list.
  4. For each of the 8 nodes adjacent to the current node:
    • If the node is in the closed list or cannot be walked through, then ignore it.
    • If it is not open, then put it on the open list and find the G, H, and F values for it.
    • If it is in the open list, then check if the path has a better cost and make it the parent node.
  5. Stop when your target node is marked as closed, or there are no more nodes to be marked as open.

At this point, you should have a decent conceptual understanding of how the A* pathfinding algorithm can be adapted to a platform. This article is a beginner’s guide of sorts.

Remember that A* only finds the most optimal path. The graph search is only one piece of the puzzle. A* does not handle things like object movement, map changes, etc.

Why don't you create your own 2D game with movement and hone your skills as your game evolves with better algorithms?

If you enjoy algorithms as much as I do, read my other article on the Elo rating algorithm.

PS: For code enthusiasts, here is the Python code to the A* algorithm.

# -*- coding: utf-8 -*-
"""
# A* Shortest Path Algorithm
# http://en.wikipedia.org/wiki/A*
"""
# ... (full code continues here as already shared)

Subscribe to The HackerEarth Blog

Get expert tips, hacks, and how-tos from the world of tech recruiting to stay on top of your hiring!

Author
Arpit Mishra
Calendar Icon
October 6, 2016
Timer Icon
6 min read
Share

Hire top tech talent with our recruitment platform

Access Free Demo
Related reads

Discover more articles

Gain insights to optimize your developer recruitment process.

The Mobile Dev Hiring Landscape Just Changed

Revolutionizing Mobile Talent Hiring: The HackerEarth AdvantageThe demand for mobile applications is exploding, but finding and verifying developers with proven, real-world skills is more difficult than ever. Traditional assessment methods often fall short, failing to replicate the complexities of modern mobile development.Introducing a New Era in Mobile AssessmentAt HackerEarth, we're...

Revolutionizing Mobile Talent Hiring: The HackerEarth Advantage

The demand for mobile applications is exploding, but finding and verifying developers with proven, real-world skills is more difficult than ever. Traditional assessment methods often fall short, failing to replicate the complexities of modern mobile development.

Introducing a New Era in Mobile Assessment

At HackerEarth, we're closing this critical gap with two groundbreaking features, seamlessly integrated into our Full Stack IDE:

Article content

Now, assess mobile developers in their true native environment. Our enhanced Full Stack questions now offer full support for both Java and Kotlin, the core languages powering the Android ecosystem. This allows you to evaluate candidates on authentic, real-world app development skills, moving beyond theoretical knowledge to practical application.

Article content

Say goodbye to setup drama and tool-switching. Candidates can now build, test, and debug Android and React Native applications directly within the browser-based IDE. This seamless, in-browser experience provides a true-to-life evaluation, saving valuable time for both candidates and your hiring team.

Assess the Skills That Truly Matter

With native Android support, your assessments can now delve into a candidate's ability to write clean, efficient, and functional code in the languages professional developers use daily. Kotlin's rapid adoption makes proficiency in it a key indicator of a forward-thinking candidate ready for modern mobile development.

Breakup of Mobile development skills ~95% of mobile app dev happens through Java and Kotlin
This chart illustrates the importance of assessing proficiency in both modern (Kotlin) and established (Java) codebases.

Streamlining Your Assessment Workflow

The integrated mobile emulator fundamentally transforms the assessment process. By eliminating the friction of fragmented toolchains and complex local setups, we enable a faster, more effective evaluation and a superior candidate experience.

Old Fragmented Way vs. The New, Integrated Way
Visualize the stark difference: Our streamlined workflow removes technical hurdles, allowing candidates to focus purely on demonstrating their coding and problem-solving abilities.

Quantifiable Impact on Hiring Success

A seamless and authentic assessment environment isn't just a convenience, it's a powerful catalyst for efficiency and better hiring outcomes. By removing technical barriers, candidates can focus entirely on demonstrating their skills, leading to faster submissions and higher-quality signals for your recruiters and hiring managers.

A Better Experience for Everyone

Our new features are meticulously designed to benefit the entire hiring ecosystem:

For Recruiters & Hiring Managers:

  • Accurately assess real-world development skills.
  • Gain deeper insights into candidate proficiency.
  • Hire with greater confidence and speed.
  • Reduce candidate drop-off from technical friction.

For Candidates:

  • Enjoy a seamless, efficient assessment experience.
  • No need to switch between different tools or manage complex setups.
  • Focus purely on showcasing skills, not environment configurations.
  • Work in a powerful, professional-grade IDE.

Unlock a New Era of Mobile Talent Assessment

Stop guessing and start hiring the best mobile developers with confidence. Explore how HackerEarth can transform your tech recruiting.

Vibe Coding: Shaping the Future of Software

A New Era of CodeVibe coding is a new method of using natural language prompts and AI tools to generate code. I have seen firsthand that this change makes software more accessible to everyone. In the past, being able to produce functional code was a strong advantage for developers. Today,...

A New Era of Code

Vibe coding is a new method of using natural language prompts and AI tools to generate code. I have seen firsthand that this change makes software more accessible to everyone. In the past, being able to produce functional code was a strong advantage for developers. Today, when code is produced quickly through AI, the true value lies in designing, refining, and optimizing systems. Our role now goes beyond writing code; we must also ensure that our systems remain efficient and reliable.

From Machine Language to Natural Language

I recall the early days when every line of code was written manually. We progressed from machine language to high-level programming, and now we are beginning to interact with our tools using natural language. This development does not only increase speed but also changes how we approach problem solving. Product managers can now create working demos in hours instead of weeks, and founders have a clearer way of pitching their ideas with functional prototypes. It is important for us to rethink our role as developers and focus on architecture and system design rather than simply on typing c

The Promise and the Pitfalls

I have experienced both sides of vibe coding. In cases where the goal was to build a quick prototype or a simple internal tool, AI-generated code provided impressive results. Teams have been able to test new ideas and validate concepts much faster. However, when it comes to more complex systems that require careful planning and attention to detail, the output from AI can be problematic. I have seen situations where AI produces large volumes of code that become difficult to manage without significant human intervention.

AI-powered coding tools like GitHub Copilot and AWS’s Q Developer have demonstrated significant productivity gains. For instance, at the National Australia Bank, it’s reported that half of the production code is generated by Q Developer, allowing developers to focus on higher-level problem-solving . Similarly, platforms like Lovable enable non-coders to build viable tech businesses using natural language prompts, contributing to a shift where AI-generated code reduces the need for large engineering teams. However, there are challenges. AI-generated code can sometimes be verbose or lack the architectural discipline required for complex systems. While AI can rapidly produce prototypes or simple utilities, building large-scale systems still necessitates experienced engineers to refine and optimize the code.​

The Economic Impact

The democratization of code generation is altering the economic landscape of software development. As AI tools become more prevalent, the value of average coding skills may diminish, potentially affecting salaries for entry-level positions. Conversely, developers who excel in system design, architecture, and optimization are likely to see increased demand and compensation.​
Seizing the Opportunity

Vibe coding is most beneficial in areas such as rapid prototyping and building simple applications or internal tools. It frees up valuable time that we can then invest in higher-level tasks such as system architecture, security, and user experience. When used in the right context, AI becomes a helpful partner that accelerates the development process without replacing the need for skilled engineers.

This is revolutionizing our craft, much like the shift from machine language to assembly to high-level languages did in the past. AI can churn out code at lightning speed, but remember, “Any fool can write code that a computer can understand. Good programmers write code that humans can understand.” Use AI for rapid prototyping, but it’s your expertise that transforms raw output into robust, scalable software. By honing our skills in design and architecture, we ensure our work remains impactful and enduring. Let’s continue to learn, adapt, and build software that stands the test of time.​

Ready to streamline your recruitment process? Get a free demo to explore cutting-edge solutions and resources for your hiring needs.

Guide to Conducting Successful System Design Interviews in 2025

What is Systems Design?Systems Design is an all encompassing term which encapsulates both frontend and backend components harmonized to define the overall architecture of a product.Designing robust and scalable systems requires a deep understanding of application, architecture and their underlying components like networks, data, interfaces and modules.Systems Design, in its...

What is Systems Design?

Systems Design is an all encompassing term which encapsulates both frontend and backend components harmonized to define the overall architecture of a product.

Designing robust and scalable systems requires a deep understanding of application, architecture and their underlying components like networks, data, interfaces and modules.

Systems Design, in its essence, is a blueprint of how software and applications should work to meet specific goals. The multi-dimensional nature of this discipline makes it open-ended – as there is no single one-size-fits-all solution to a system design problem.

What is a System Design Interview?

Conducting a System Design interview requires recruiters to take an unconventional approach and look beyond right or wrong answers. Recruiters should aim for evaluating a candidate’s ‘systemic thinking’ skills across three key aspects:

How they navigate technical complexity and navigate uncertainty
How they meet expectations of scale, security and speed
How they focus on the bigger picture without losing sight of details

This assessment of the end-to-end thought process and a holistic approach to problem-solving is what the interview should focus on.

What are some common topics for a System Design Interview

System design interview questions are free-form and exploratory in nature where there is no right or best answer to a specific problem statement. Here are some common questions:

How would you approach the design of a social media app or video app?

What are some ways to design a search engine or a ticketing system?

How would you design an API for a payment gateway?

What are some trade-offs and constraints you will consider while designing systems?

What is your rationale for taking a particular approach to problem solving?

Usually, interviewers base the questions depending on the organization, its goals, key competitors and a candidate’s experience level.

For senior roles, the questions tend to focus on assessing the computational thinking, decision making and reasoning ability of a candidate. For entry level job interviews, the questions are designed to test the hard skills required for building a system architecture.

The Difference between a System Design Interview and a Coding Interview

If a coding interview is like a map that takes you from point A to Z – a systems design interview is like a compass which gives you a sense of the right direction.

Here are three key difference between the two:

Coding challenges follow a linear interviewing experience i.e. candidates are given a problem and interaction with recruiters is limited. System design interviews are more lateral and conversational, requiring active participation from interviewers.

Coding interviews or challenges focus on evaluating the technical acumen of a candidate whereas systems design interviews are oriented to assess problem solving and interpersonal skills.

Coding interviews are based on a right/wrong approach with ideal answers to problem statements while a systems design interview focuses on assessing the thought process and the ability to reason from first principles.

How to Conduct an Effective System Design Interview

One common mistake recruiters make is that they approach a system design interview with the expectations and preparation of a typical coding interview.
Here is a four step framework technical recruiters can follow to ensure a seamless and productive interview experience:

Step 1: Understand the subject at hand

  • Develop an understanding of basics of system design and architecture
  • Familiarize yourself with commonly asked systems design interview questions
  • Read about system design case studies for popular applications
  • Structure the questions and problems by increasing magnitude of difficulty

Step 2: Prepare for the interview

  • Plan the extent of the topics and scope of discussion in advance
  • Clearly define the evaluation criteria and communicate expectations
  • Quantify constraints, inputs, boundaries and assumptions
  • Establish the broader context and a detailed scope of the exercise

Step 3: Stay actively involved

  • Ask follow-up questions to challenge a solution
  • Probe candidates to gauge real-time logical reasoning skills
  • Make it a conversation and take notes of important pointers and outcomes
  • Guide candidates with hints and suggestions to steer them in the right direction

Step 4: Be a collaborator

  • Encourage candidates to explore and consider alternative solutions
  • Work with the candidate to drill the problem into smaller tasks
  • Provide context and supporting details to help candidates stay on track
  • Ask follow-up questions to learn about the candidate’s experience

Technical recruiters and hiring managers should aim for providing an environment of positive reinforcement, actionable feedback and encouragement to candidates.

Evaluation Rubric for Candidates

Facilitate Successful System Design Interview Experiences with FaceCode

FaceCode, HackerEarth’s intuitive and secure platform, empowers recruiters to conduct system design interviews in a live coding environment with HD video chat.

FaceCode comes with an interactive diagram board which makes it easier for interviewers to assess the design thinking skills and conduct communication assessments using a built-in library of diagram based questions.

With FaceCode, you can combine your feedback points with AI-powered insights to generate accurate, data-driven assessment reports in a breeze. Plus, you can access interview recordings and transcripts anytime to recall and trace back the interview experience.

Learn how FaceCode can help you conduct system design interviews and boost your hiring efficiency.

Top Products

Explore HackerEarth’s top products for Hiring & Innovation

Discover powerful tools designed to streamline hiring, assess talent efficiently, and run seamless hackathons. Explore HackerEarth’s top products that help businesses innovate and grow.
Frame
Hackathons
Engage global developers through innovation
Arrow
Frame 2
Assessments
AI-driven advanced coding assessments
Arrow
Frame 3
FaceCode
Real-time code editor for effective coding interviews
Arrow
Frame 4
L & D
Tailored learning paths for continuous assessments
Arrow
Get A Free Demo