URL:
<http://gna.org/patch/?3122>
Summary: Simpler pathfinding
Project: Battle for Wesnoth
Submitted by: jamit
Submitted on: Sun 05 Feb 2012 03:57:14 PM EST
Priority: 5 - Normal
Status: None
Privacy: Public
Assigned to: None
Originator Email:
Open/Closed: Open
Discussion Lock: Any
_______________________________________________________
Details:
I was looking around the codebase, orienting myself, when I noticed that the
path generation in find_routes(), pathfind.cpp, was a bit more complicated
than necessary. It appears to be based on Dijkstra's algorithm, which solves
graphs with edge-weights. Since Wesnoth movement has vertex-weights instead, a
simpler greedy algorithm can be used (as someone had already noted in the
comments). I do not know how much of a savings this would be, but it does
eliminate a temporary variable created for each hex evaluated for being in
range. Since it looks like this function is called fairly often, this
optimization might be useful.
While I was at it, I converted some names to be more meaningful and threw in
some comments explaining how things work.
Anyway, it seems to work correctly and in theory should be faster (I didn't do
any profiling though), so I am submitting it here for consideration for the
official game.
_______________________________________________________
File Attachments:
-------------------------------------------------------
Date: Sun 05 Feb 2012 03:57:14 PM EST Name: simpler-paths.diff Size: 12kB
By: jamit
Revised find_routes() and associated structs
<http://gna.org/patch/download.php?file_id=15017>
_______________________________________________________
Reply to this item at:
<http://gna.org/patch/?3122>
_______________________________________________
Message sent via/by Gna!
http://gna.org/
_______________________________________________
Wesnoth-bugs mailing list
[email protected]
https://mail.gna.org/listinfo/wesnoth-bugs
