DEV Community: Gitesh Talapady

Implementing A* Search on a Grid-Based Path-Finding Map with Obstacle Avoidance

Gitesh Talapady — Tue, 06 Oct 2026 14:35:33 +0000

Introduction
Path finding is a fundamental problem in Artificial Intelligence and computer science. The objective of path finding is to determine a suitable route between a starting point and a destination while considering restrictions such as obstacles or blocked areas.
Path-finding algorithms are commonly used in video games, robotics, navigation systems, warehouse automation, and autonomous vehicles. One of the most popular algorithms for solving this problem is A (A-star) Search*.
A* Search combines the actual distance already travelled with an estimated distance to the destination. This allows it to efficiently search for a path while avoiding unnecessary areas of the map.

Representing the Map as a Grid
For this implementation, the environment can be represented using a two-dimensional grid. Each cell represents a possible position.

For example:
S . . # .
. # . # .
. # . . .
. . # . .

. . . G

Here:
S represents the starting position.
G represents the goal.
. represents a free cell.

represents an obstacle.

The objective is to find a path from S to G without passing through the obstacle cells.

What is A* Search?
A* Search is an informed search algorithm that uses a cost function:
f(n) = g(n) + h(n)
where:
g(n) represents the actual cost of reaching the current cell from the starting point.
h(n) represents the estimated cost from the current cell to the goal.
f(n) represents the total estimated cost of the path through that cell.
The algorithm selects the cell with the lowest estimated total cost and continues searching from there.

Heuristic Function
The heuristic is one of the most important components of A* Search. For a grid where movement is allowed only horizontally and vertically, Manhattan distance can be used.

The formula is: h(n)=|x_1-x_2|+|y_1-y_2|
where (x₁, y₁) represents the current position and (x₂, y₂) represents the goal.

For example, if the current position is (2,3) and the goal is (5,6):
h(n)=|2-5|+|3-6|
h(n)=3+3=6
Thus, the estimated distance to the goal is 6 steps.

Working of A* Search
The algorithm begins at the starting cell and examines its neighboring cells.
For each possible neighboring cell:
Check whether the cell is inside the grid.
Check whether it is an obstacle.
Calculate the movement cost.
Calculate the heuristic cost.
Calculate the total cost using:
f(n)=g(n)+h(n)
Select the most promising cell.
Continue the process until the goal is reached.
Once the goal is found, the algorithm traces the selected cells backward to reconstruct the final path.

Obstacle Avoidance
Obstacle avoidance is an important part of the implementation. When A* encounters a cell containing an obstacle, it simply ignores that cell and evaluates other available neighboring cells.

For example:
S . . . .

# # .

. . . . G
The algorithm cannot move directly through the blocked cells. Instead, it searches for an alternative route around them.

A possible path can be represented as:
S → → → →
↓
← ← ← ← G
The actual path depends on the location of the obstacles and the movement rules defined for the grid.

Basic Algorithm
The implementation of A* can be summarized as follows:
Create the grid.
Mark the starting and goal positions.
Mark blocked cells as obstacles.
Add the starting cell to the open list.
Select the cell having the lowest f(n) value.
Examine its neighboring cells.
Ignore invalid or blocked cells.
Calculate g(n), h(n), and f(n).
Add suitable cells to the search list.
Repeat until the goal is reached.
Trace the parent cells to obtain the final path.

Applications
A* Search has several practical applications:
Video games: Finding routes for characters and enemies.
Robotics: Helping robots navigate around obstacles.
GPS and navigation: Finding efficient routes between locations.
Warehouse automation: Guiding automated vehicles around shelves.
Autonomous systems: Planning movement through an environment.
Maze solving: Finding paths through blocked environments.

Advantages
A* Search offers several advantages:
It can find an optimal path when an appropriate heuristic is used.
It considers obstacles during path planning.
It is generally more efficient than uninformed search methods.
It can be implemented on simple grid-based maps.
Its working can be visualized easily.

Limitations
A* may require considerable memory because it stores information about the cells being explored. Its performance also depends on the heuristic function used. A poorly selected heuristic can result in unnecessary exploration and slower execution.

Conclusion
A* Search is an important path-finding technique that combines actual movement cost with an estimated distance to the destination. When implemented on a grid, it can effectively find a route while avoiding obstacles. Because of its efficiency and practical applications, A* is widely used in artificial intelligence, games, robotics, navigation, and autonomous systems.

Simulating Trie Data Structure: Building a Search-as-You-Type Engine

Gitesh Talapady — Tue, 06 Oct 2026 14:29:37 +0000

Introduction
In today's digital world, searching for information has become an essential part of almost every software application. Whether we are searching for a product on an e-commerce website, a contact on a smartphone, or a word in a search engine, applications often provide suggestions while we type. This feature is commonly known as search-as-you-type or autocomplete.
Behind this simple-looking feature, efficient data structures are required to quickly find words that match the characters entered by the user. One of the most suitable data structures for this purpose is the Trie, also known as a Prefix Tree.
A Trie stores words in a tree-like structure where each node represents a character. It is particularly useful for searching words based on prefixes, making it an excellent choice for implementing an autocomplete system.

Understanding the Trie Data Structure
A Trie consists of nodes connected to one another. Each node represents a character, and a complete word is identified by marking its final character as the end of a word.
Consider the following word list:
Apple
Application
Apply
App
Banana
Ball
The words beginning with "App" share the same path in the Trie. Therefore, when a user enters app, the system can directly reach the corresponding node and find all the words stored below it.
This is different from a traditional linear search, where the application may need to compare the entered prefix with every word in the list.

How a Search-as-You-Type Engine Works
The implementation can be divided into two major operations: insertion and search.

Inserting Words
First, all words from the word list are inserted into the Trie. Each word is processed character by character.
For example, while inserting the word "apple", nodes are created for:
a → p → p → l → e
If another word such as "application" is inserted, the existing a → p → p path can be reused.
Searching for a Prefix
When a user types a prefix, the Trie follows the corresponding characters.
For example:
User enters: app

The Trie navigates through:
a → p → p

After reaching the app node, the system explores the remaining branches and produces suggestions such as:
app
apple
application
apply
This makes the search process efficient, especially when the dictionary contains thousands or millions of words.

Example:
Suppose our word list contains:
apple
application
apply
app
banana
ball
bat

If the user enters:
ba

the autocomplete system can return:
banana
ball
bat

If the user enters:
app

the system returns:
app
apple
application
apply
Thus, the Trie provides a natural way of organizing words according to their prefixes.

Algorithm
The basic algorithm for a Trie-based autocomplete system is:
Create an empty Trie.
Insert every word from the word list.
Accept a prefix from the user.
Traverse the Trie according to the characters of the prefix.
If the prefix does not exist, display "No suggestions found."
If the prefix exists, traverse its child nodes.
Collect all complete words.
Display the collected words as suggestions.

Applications
Trie-based search is useful in many real-world applications, including:
Search engine autocomplete
Mobile keyboard suggestions
Dictionary and spell-checking applications
Contact search
E-commerce product search
Code editors and IDEs
File and directory search systems
Command-line autocomplete

Advantages
The main advantage of a Trie is its efficient prefix-based searching capability. It does not need to compare the complete prefix against every word individually. It also allows words having common prefixes to share nodes.

Other advantages include:
Fast prefix searching
Suitable for autocomplete systems
Easy retrieval of all words with a given prefix
Effective for large dictionaries
Simple and logical tree-based structure

Limitations
Although Tries are efficient, they can require more memory because every character may be represented by a separate node. For very large dictionaries, memory optimization techniques may therefore be required.

Conclusion:
The Trie data structure provides an efficient solution for building a search-as-you-type engine. By storing words according to their prefixes, it can quickly identify matching words and generate suggestions. This concept demonstrates how selecting an appropriate data structure can significantly improve the performance of a software application. Trie-based searching continues to be useful in search engines, keyboards, dictionaries, and many other systems where fast prefix matching is required.