How far does it scale currently? If you get close, some tweaks may help. If you approach doesn't scale at all (which I suspect), you'll need to reconsider the approach in general.

Some ideas:

1. BFS uses more memory than DFS (e.g. A*), as you need to keep more data in memory. For this problem, you could prioritize moves that go into the general direction.

2. String keys seem to be quite wasteful. Consider using a specialized data structure for sparse 2d arrays (I have implemented one here, you'll probably find more / better ones on the net). Or use a Position2D hash key.

3. Do you need all this data in Position?

4. Can you exploit the structure of the moves in some way? Are there some constraints that you can exploit? Do you need the full grid?

5. The potential moves form a graph and you could run Dijkstra on this graph (without materializing the Graph) (if your algorithm is not equivalent already). I doubt that BFS will work here due to the memory requirements though.

How far does it scale currently? If you get close, some tweaks may help. If you approach doesn't scale at all (which I suspect), you'll need to reconsider the approach in general.

Some ideas:

1. BFS uses more memory than DFS (e.g. A*), as you need to keep more data in memory. For this problem, you could prioritize moves that go into the general direction.

2. String keys seem to be quite wasteful. Consider using a specialized data structure for sparse 2d arrays (I have implemented one here, you'll probably find more / better ones on the net). Or use a Position2D hash key.

3. Do you need all this data in Position?

4. Can you exploit the structure of the moves in some way? Are there some constraints that you can exploit? Do you need the full grid?

How far does it scale currently? If you get close, some tweaks may help. If you approach doesn't scale at all (which I suspect), you'll need to reconsider the approach in general.

Some ideas:

1. BFS uses more memory than DFS (e.g. A*), as you need to keep more data in memory. In particular for this problem, you could prioritize moves that go into the general direction.

2. String keys seem to be quite wasteful. Consider using a specialized data structure for sparse 2d arrays (I have implemented one here, you'll probably find more / better ones on the net). Or use a Position2D hash key.

3. Do you need all this data in Position?

4. Can you exploit the structure of the moves in some way? Are there some constraints that you can exploit? Do you need the full grid?

How far does it scale currently? If you get close, some tweaks may help. If you approach doesn't scale at all (which I suspect), you'll need to reconsider the approach in general.

Some ideas:

1. BFS uses more memory than DFS (e.g. A*), as you need to keep more data in memory. For this problem, you could prioritize moves that go into the general direction.

2. String keys seem to be quite wasteful. Consider using a specialized data structure for sparse 2d arrays (I have implemented one here, you'll probably find more / better ones on the net). Or use a Position2D hash key.

3. Do you need all this data in Position?

4. Can you exploit the structure of the moves in some way? Are there some constraints that you can exploit? Do you need the full grid?

5. The potential moves form a graph and you could run Dijkstra on this graph (without materializing the Graph) (if your algorithm is not equivalent already). I doubt that BFS will work here due to the memory requirements though.