4
$\begingroup$

I am working on a project which maps to a variant of path finding problem. I am new to this area and I would be very grateful if you could give suggestions/ point to libraries for relevant algorithms.

A simplified version of my problem statement is as follows-

Goal: On a 2D grid, starting from a fixed point reach the destination in exactly N steps.

Allowed actions: 1. At every position, you have a choice of up to three moves (i.e. straight, curve left, curve right). 2. You cannot collide with the path traveled so far (just like in the snake game).

Dimension of the grid: N x N where N is between 100-1000

Scalable: Later on, the problem will be scaled to have multiple such snakes going between different pairs of points on the grid. The ultimate goal is to get ALL snakes to reach their respective destinations in a fixed number of steps without any collisions.

TL;DR: Essentially I have to find a fixed length path on a dynamically generated directed graph. Is there a better choice than a A* / greedy heuristic? Is it worth taking a Q- learning approach?

A rudimentary one snake version written in python can be found here - Github Link Thanks in advance!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.