A* Pathfinding in OpenXTalk

[xAction]

RED HOT v8 update (up to) 200x200 grid, super fast PPM image rendering

AStar_Pathfinding_v8b_PPM.oxtStack

(33.53 KiB) Downloaded 10 times

AStarPathFinding_v8.gif (181.04 KiB) Viewed 189 times

But ...eh still 37 ms to scan the maze

Now with quadrants.
Still unsatisfied with the results, so many things that could be solved and it doesnt solve them.
Something about the heuristics...and tie breaking. I'm too burned out to think about it.

This stack:

1. generates a base GridArray of 1s and 0s
2. Splits the grid into 4 quadrants centered around the starting point
3. Tries to search them all if the first main GridArray produces no path.
4. The grids are modified (from 1 and 0) with some characters to indicate what is going on:
   • unsearched/empty
   • searched/neighbor
   • blocked,
   • the path
   • visited
5. Then it combines everything into a final array VisualGrid
6. The VisualGrid array is read and converted into a PPM image

Ah , right, so I noticed that it sometimes walks through obstacles. I don't know why.

You can now click on the map, or return/enter in the fiels to initiate the test

[tperry2x]

I'm seeing this and instantly thinking of implementing something like Command & Conquer (OpenRA), where you click on an area and a game object is able to 'travel' there, picking it's way around obstacles.

Of course, this happens in realtime in many games - what if something else moves into the way of the calculated path of travel?

I'm wondering if it's better to calculate each move as an iteration. (Sudo-sudo-code in the back of my head):

object I want to move is at xy loc of 100,100..
I click at 300,500

The object works out that it has to travel across the screen at 200px and 400px to the right.
So it can start moving straight away with no delay.
If something is in the way, then work out how to get around that particular obstacle, and move onto the next step.

After all, it knows where it ultimately wants to get to...

sorry that's so rough an idea, trying to multitask is never a good thing

[xAction]

Every turn of the game (or less, really, no need for AI to be psychopathic and perniciously swarm a target) you run the A* PathFinding again.
You plug every moved obstacle/whatever into the current grid

Ideally on a localized grid, this is just EXTREME testing.
To minimize the time it takes to solve the grid you save the default open positions and only search those in any repeated scan.

The first solution for some game avatar is to find if there's any valid path at all.
Foremost, have to avoid being completely blocked in at the spawn point.

Then if there is no valid path but there's somewhere to go, find the nearest open point, move as per usual dummy style -1 or +1 in x and/or y

Then run the path finding again (each turn), with the new starting location.

In a "ChatGPT is hunting me in a maze" type Terminator game you have to update the end position because the player moved.

I am not happy at all with the results of this test, the All Powerful AI gave me like 20 things I could do different if I wanted to become a Wizard of A*, so over my head ...ugh.

Updating stack in Top post in a second.

[xAction]

A Star Test2_2016.livecode

(1.12 MiB) Downloaded 8 times

SUPER_SLOW_ASTAR_PATHFINDING.png (36.69 KiB) Viewed 161 times

This is not my stack, there are many like it, this one is not mine, but as it was created during the great golden age of Open Source so it is now ours and we can rebuild and make it better, we have the technology.

It creates 10003 graphics to map the A* routine. Takes...I dunno, 16 minutes? Well let's find out.
Well I started it, made coffee, made breakfast, ate breakfast, came back to check on it, left to relieve myself, came back to check on it...still going...had two cups of coffee.

My computer was so taxed the monitor stopped wanted to display and sure feels like the temperature in the room went up a few degrees.

Oh and I probably got logged out of the forum, so I better copy this text someplace safe.
And it completed without reporting the time taken as instructed, WTF?
Guess it ran out of memory or something.

I'm just preserving it here for the moment in all of it's awful glory.