A* Search with Custom Heuristics and Neighbor Functions for Versatile Solutions

Recently, while searching for a solution to a complex problem, I stumbled upon a code implementation that caught my attention. With a little tweaking and generalization, I was able to simplify the code and create a versatile solution that I believe is worth sharing.

It utilized custom heuristic and neighbor functions to estimate costs and determine connectivity between points in the problem space. This customization offered a level of adaptability and I realized its potential for solving a variety of problems.

While the original implementation was most helpful resource on the internet, I aimed to simplify it further. By eliminating unnecessary complexity and streamlining the code, ensuring that the code could be understood and utilized by a broader audience. I hope to provide an alternative viewpoint and contribute to the pool of resources available for problem solving.

The resource I am sharing consists of two essential parts: the search function and the accompanying test suite. The search function lies at the core of the implementation, offering a flexible and adaptable approach to problem solving. It utilizes custom heuristic and neighbor functions to navigate through the problem space and find optimal solutions. The test suite, on the other hand, serves as a valuable tool to verify the correctness and functionality of the search function.

Function definition is

function search(startPositions, {
    getNeighbors,
    heuristic,
    maxPathLength,
    isGoal,
})

where startPositions is array of searchable states, getNeigbors is function that is passed and returns adjacent positions:

(position)=>[neigborPosition,neigborPosition....]

heuristic is function that returns the quality of current position, smaller is better, when it reaches 0 you found your solution, in number space it would be:

(position)=>Math.abs(position - goal)

maxPathLength is number of the max depth of search. isGoal is alternative function for case where you want to finish your search on some other condition other than heuristic returns 0:

(position)=>position == goal

Let me show you one of the tests:

    it('minimal search', function () {
        function heuristic(position){
            return Math.abs(10 - position)
        }
        function getNeighbors(position){
            return [position + 8, position - 3]
        }
        let res = search([0],{getNeighbors,heuristic})
        assert.equal(res.pop(),0)
        assert.equal(res.pop(),8)
        assert.equal(res.pop(),5)
        assert.equal(res.pop(),13)
        assert.equal(res.pop(),10)
    });

Feel free to checkout the original solution and my try on it: [GitHub aStar.js] (https://github.com/slobacartoonac/js_lib/blob/main/search/aStar.js) And tests: [GitHub aStar.js tests] (https://github.com/slobacartoonac/js_lib/blob/main/test/test_a_star.js)

All the feedback is welcome :) Please note that I am not native speaker, and I don't write much.

Post added

For folks that love types I added d.ts:

type GetNeighborsFunction<T> = (position: T) => T[];
type HeuristicFunction<T> = (position: T) => number;
type IsGoalFunction<T> = (position: T) => boolean;

interface AStarOptions<T> {
  getNeighbors: GetNeighborsFunction<T>;
  heuristic: HeuristicFunction<T>;
  maxPathLength?: number;
  isGoal?: IsGoalFunction<T>;
  allowDeep?: boolean;
}

export function search<T>(
  startPositions: T[],
  options: AStarOptions<T>
): T[];

More about my approach for using js and ts together: Approach blog post