POV-Ray : Newsgroups : povray.advanced-users : A-Star algorithm Image Test Server Time
15 Oct 2024 17:20:02 EDT (-0400)
  A-Star algorithm Image Test (Message 1 to 5 of 5)  
From: Bald Eagle
Subject: A-Star algorithm Image Test
Date: 9 Sep 2023 13:20:00
Message: <web.64fca905c32c9bfa1f9dae3025979125@news.povray.org>
So, I grabbed some code off the wayback machine for the A* algorithm in visual
c++, and converted all of that to POV-Ray SDL.

Although I still probably need to go back in and fix some the
late-night/early-morning edits/hacks that I did in order to get it to run to
completion without errors, it looks like it works.

After hand-coding some obstacles in the map array, I figured that I ought to try
it with a real maze, and the easiest thing to do there was use an image (plus
that would move me in the direction of applying this to meshes)

So after a few false starts, I got everything nicely framed on the page, and it
took this implementation 2 min 20 sec to solve a 500*500 pixel maze image (parse
& render).

Enjoy.

- BE


Post a reply to this message


Attachments:
Download 'a-star image.png' (805 KB)

Preview of image 'a-star image.png'
a-star image.png


 

From: jr
Subject: Re: A-Star algorithm Image Test
Date: 9 Sep 2023 13:40:00
Message: <web.64fcadbe7648a5e8b180e2cc6cde94f1@news.povray.org>
hi,

"Bald Eagle" <cre### [at] netscapenet> wrote:
> So, ... Enjoy.

wow.  _v_ cool.  (I'm turning that shade of green again.. :-))

hope you'll publish "a tutorial" on the topic.


regards, jr.


Post a reply to this message

From: Bald Eagle
Subject: Re: A-Star algorithm Image Test
Date: 9 Sep 2023 16:15:00
Message: <web.64fcd1f97648a5e81f9dae3025979125@news.povray.org>
"jr" <cre### [at] gmailcom> wrote:

> wow.  _v_ cool.  (I'm turning that shade of green again.. :-))

Hi jr,
I just took a stab at it, and had a few moments where I was feeling like I had
bit off more than I could chew. As you can imagine, I get that feeling often.

I kinda get how it works - the gist - but there are a few things that I haven't
cleared up, and I haven't looked at the binary heap optimization part.
I basically just edited the code and kept running it and hacking it until it ran
without errors.

> hope you'll publish "a tutorial" on the topic.

I will not, until I have something significantly different from the code I
copied.

https://web.archive.org/web/20051230122239/http://www.policyalmanac.org/games/aStarTutorial.htm
code:
https://web.archive.org/web/20051230122239/http://www.blitzcoder.com/cgi-bin/showcase/showcase_showentry.pl?id=turtle17
7604062002002208&comments=no

Other stuff at:

http://theory.stanford.edu/~amitp/GameProgramming/

Sebastian Lague:  https://www.youtube.com/watch?v=mZfyt03LDH4

Daniel Schiffman: https://www.youtube.com/watch?v=EaZxUCWAjb0

Now with regard to TdG's desire to erode terrain, I wanted to find a heightfield
that I could use to run a height-driven A* algorithm on, and wouldn't you know
it - I found a bunch of interesting links.

https://ranmantaru.com/blog/2011/10/08/water-erosion-on-heightmap-terrain/

https://github.com/dandrino/terrain-erosion-3-ways

Sebastian Lague:  https://www.youtube.com/watch?v=eaXk97ujbPQ

https://github.com/LanLou123/Webgl-Erosion

https://jobtalle.com/simulating_hydraulic_erosion.html

https://perso.liris.cnrs.fr/aparis/public_html/posts/terrain_erosion.html

and lots more, I'm sure.

Since this is essentially a cost-optimization algorithm, I was also thinking
that maybe this kind of thing could be used to trace electrical circuits, or
something like that.

Also, conducting erosion on a 3D objects could give more interesting clouds if
rendered as a df3.

- BW


Post a reply to this message

From: William F Pokorny
Subject: Re: A-Star algorithm Image Test
Date: 10 Sep 2023 06:46:25
Message: <64fd9e81$1@news.povray.org>
On 9/9/23 13:19, Bald Eagle wrote:
> After hand-coding some obstacles in the map array, I figured that I ought to try
> it with a real maze, and the easiest thing to do there was use an image (plus
> that would move me in the direction of applying this to meshes)

Cool! :-)

Bill P.


Post a reply to this message

From: kurtz le pirate
Subject: Re: A-Star algorithm Image Test
Date: 10 Sep 2023 09:42:04
Message: <64fdc7ac$1@news.povray.org>
On 09/09/2023 19:19, Bald Eagle wrote:
> So, I grabbed some code off the wayback machine for the A* algorithm in visual
> c++, and converted all of that to POV-Ray SDL.
> 
> Although I still probably need to go back in and fix some the
> late-night/early-morning edits/hacks that I did in order to get it to run to
> completion without errors, it looks like it works.
> 
> After hand-coding some obstacles in the map array, I figured that I ought to try
> it with a real maze, and the easiest thing to do there was use an image (plus
> that would move me in the direction of applying this to meshes)
> 
> So after a few false starts, I got everything nicely framed on the page, and it
> took this implementation 2 min 20 sec to solve a 500*500 pixel maze image (parse
> & render).
> 
> Enjoy.
> 
> - BE
> 


How brave ! Very good job Bill


-- 
Kurtz le pirate
Compagnie de la Banquise


Post a reply to this message

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.