[pgrouting-dev] Ask how to use : Euclidean distance heuristic in A* in pgrouting

[Steve Horn]

Robi,
Since you have the instructions on how to recompile, I can tell you that
the heuristic function can be changed in the file astar_boost_wrapper.cpp
in the core/src directory around line 82. Look for the comment:

//You can choose any heuristical function from below
//return ::max(dx, dy);
//return ::sqrt(dx * dx + dy * dy)/4;
//return 0;
return (::fabs(dx)+::fabs(dy))/2;

On Tue, Jul 10, 2012 at 3:20 AM, Sanak <geosanak at gmail.com> wrote:

> Hi Robi,
>
> I am not familiar with A* heuristic logic,
> but if you want to build pgRouting Windows binary,
> see following source and docs.
>
> https://github.com/sanak/pgrouting
> https://github.com/sanak/pgrouting/blob/mingw/BUILD.mingw
> https://github.com/sanak/pgrouting/blob/mingw/BUILD.mingw64
>
> And if you want to skip building dependency libraries,
> use following build environment.
>
> http://sdrv.ms/NFCgr2
>  +- Build.zip     ... for 32bit work folder. (extract to "C:\")
>  +- MinGW.zip ... for 32bit build environment. (extract to "C:\" and run
> "C:\MinGW\msys\1.0\msys.bat")
>  +- Build64.zip ... for 64bit work folder. (extract to "C:\")
>  +- ming64.zip ... for 64bit build environment. (based on PostGIS one.
> extract to "C:\" and run "C:\ming64\msys\msys.bat")
>
> Regards,
>
> 2012/7/10 Stephen Woodbridge <woodbri at swoodbridge.com>
>
>> On 7/9/2012 9:24 PM, Haruhi Suzumiya wrote:
>>
>>> Good morning,
>>>
>>> Dear mr/mrs, :)
>>>
>>> I'm robi, my username is haruhi. I'm newbie in pgrouting.
>>> I want to try use euclidean distance heuristic in A* in pgrouting, may u
>>> give me tutorial how to change the heuristic and recompile it? :)
>>> Fyi, I'm use windows 7, postgre 1.8.4, pgRouting-1.02_pg-8.3.3 :)
>>>
>>
>> Hi Robi,
>>
>> The pgRouting package already supports A* and by definition it uses a
>> euclidean distance heuristic. See the function shortest_path_astar(), there
>> also may be some wrapper function with names like astar_sp_*
>>
>> The wrapper function are just higher level convenience function.
>>
>> There are a couple of tutorials around that probably have good examples
>> of how to use the functions.
>>
>> If you want to change the heuristic, then you will need to look at the
>> Boost Graph code that is used to implement it. We don't have any
>> documentation on the implementation, but there are a lot of docs on Boost
>> Graph and you can get help from that list.
>>
>> What I would do is write a wrapper for the Boost Graph code and reads a
>> text file to input the graph, sets up the structures to pass the data to
>> algorithm to run it and then prints out the results. You can do all this
>> outside of the database which greatly simplifies debugging your changes.
>> When you have it working the way you want, then it should be a clean drop
>> in replacement for the existing code or you can clone the existing code and
>> rename it for the new algorithm.
>>
>> -Steve W
>> ______________________________**_________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>


-- 
Steve Horn
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120710/fdd6907d/attachment-0001.html>