CalcMapRoute.pm.svn-base
上传用户:market2
上传日期:2018-11-18
资源大小:18786k
文件大小:10k
源码类别:

外挂编程

开发平台:

Windows_Unix

  1. #########################################################################
  2. #  OpenKore - Calculation of inter-map routes
  3. #  Copyright (c) 2006 OpenKore Team
  4. #
  5. #  This software is open source, licensed under the GNU General Public
  6. #  License, version 2.
  7. #  Basically, this means that you're allowed to modify and distribute
  8. #  this software. However, if you distribute modified versions, you MUST
  9. #  also distribute the source code.
  10. #  See http://www.gnu.org/licenses/gpl.html for the full license.
  11. #########################################################################
  12. # This task calculates a route between different maps. When the calculation
  13. # is successfully completed, the result can be retrieved with
  14. # $Task_CalcMapRoute->getRoute() or $Task_CalcMapRoute->getRouteString().
  15. #
  16. # Note that this task only performs calculation. The MapRoute task is
  17. # responsible for actually walking from a map to another.
  18. package Task::CalcMapRoute;
  19. use strict;
  20. use Time::HiRes qw(time);
  21. use Modules 'register';
  22. use Task;
  23. use base qw(Task);
  24. use Task::Route;
  25. use Field;
  26. use Globals qw(%config $field %portals_lut %portals_los %timeout $char %routeWeights);
  27. use Translation qw(T TF);
  28. use Log qw(debug);
  29. use Utils qw(timeOut);
  30. use Utils::Exceptions;
  31. # Stage constants.
  32. use constant {
  33. INITIALIZE => 1,
  34. CALCULATE_ROUTE => 2
  35. };
  36. # Error constants.
  37. use enum qw(
  38. CANNOT_LOAD_FIELD
  39. CANNOT_CALCULATE_ROUTE
  40. );
  41. ##
  42. # Task::CalcMapRoute->new(options...)
  43. #
  44. # Create a new Task::CalcMapRoute object. The following options are allowed:
  45. # `l
  46. # - All options allowed for Task->new()
  47. # - map (required) - The map you want to go to, for example "prontera".
  48. # - x, y - The coordinate on the destination map you want to walk to. On some maps this is
  49. #          important because they're split by a river. Depending on which side of the river
  50. #          you want to be, the route may be different.
  51. # - sourceMap - The map you're coming from. If not specified, the current map
  52. #               (where the character is) is assumed.
  53. # - sourceX and sourceY - The source position where you're coming from. If not specified,
  54. #                         the character's current position is assumed.
  55. # - budget - The maximum amount of money you want to spend on walking the route (Kapra
  56. #            teleport service requires money).
  57. # - maxTime - The maximum time to spend on calculation. If not specified,
  58. #             $timeout{ai_route_calcRoute}{timeout} is assumed.
  59. # `l`
  60. sub new {
  61. my $class = shift;
  62. my %args = @_;
  63. my $self = $class->SUPER::new(@_);
  64. if (!$args{map}) {
  65. ArgumentException->throw(error => "Invalid arguments.");
  66. }
  67. $self->{source}{map} = defined($args{sourceMap}) ? $args{sourceMap} : $field->name();
  68. $self->{source}{x} = defined($args{sourceX}) ? $args{sourceX} : $char->{pos_to}{x};
  69. $self->{source}{y} = defined($args{sourceY}) ? $args{sourceY} : $char->{pos_to}{y};
  70. $self->{dest}{map} = $args{map};
  71. $self->{dest}{pos}{x} = $args{x};
  72. $self->{dest}{pos}{y} = $args{y};
  73. if ($args{budget} ne '') {
  74. $self->{budget} = $args{budget};
  75. } elsif ($config{route_maxWarpFee} ne '') {
  76. if ($config{route_maxWarpFee} > $char->{zenny}) {
  77. $self->{budget} = $char->{zenny};
  78. } else {
  79. $self->{budget} = $config{route_maxWarpFee};
  80. }
  81. }
  82. $self->{maxTime} = $args{maxTime} || $timeout{ai_route_calcRoute}{timeout};
  83. $self->{stage} = INITIALIZE;
  84. $self->{openlist} = {};
  85. $self->{closelist} = {};
  86. $self->{mapSolution} = [];
  87. $self->{solution} = [];
  88. $self->{dest}{field} = {};
  89. return $self;
  90. }
  91. # Overrided method.
  92. sub iterate {
  93. my ($self) = @_;
  94. $self->SUPER::iterate();
  95. if ($self->{stage} == INITIALIZE) {
  96. my $openlist = $self->{openlist};
  97. my $closelist = $self->{closelist};
  98. eval {
  99. $self->{dest}{field} = new Field(name => $self->{dest}{map});
  100. };
  101. if (caught('FileNotFoundException', 'IOException')) {
  102. $self->setError(CANNOT_LOAD_FIELD, TF("Cannot load field '%s'.", $self->{dest}{map}));
  103. return;
  104. } elsif ($@) {
  105. die $@;
  106. }
  107. # Check whether destination is walkable from the starting point.
  108. if ($self->{source}{map} eq $self->{dest}{map}
  109.  && Task::Route->getRoute(undef, $field, $self->{source}, $self->{dest}{pos}, 0)) {
  110. $self->{mapSolution} = [];
  111. $self->setDone();
  112. return;
  113. }
  114. # Initializes the openlist with portals walkable from the starting point.
  115. foreach my $portal (keys %portals_lut) {
  116. my $entry = $portals_lut{$portal};
  117. next if ($entry->{source}{map} ne $field->name());
  118. my $ret = Task::Route->getRoute($self->{solution}, $field, $self->{source}, $entry->{source});
  119. if ($ret) {
  120. foreach my $dest (keys %{$entry->{dest}}) {
  121. my $penalty = int(($entry->{dest}{$dest}{steps} ne '') ? $routeWeights{NPC} : $routeWeights{PORTAL});
  122. $openlist->{"$portal=$dest"}{walk} = $penalty + scalar @{$self->{solution}};
  123. $openlist->{"$portal=$dest"}{zenny} = $entry->{dest}{$dest}{cost};
  124. }
  125. }
  126. }
  127. $self->{stage} = CALCULATE_ROUTE;
  128. debug "CalcMapRoute - initialized.n", "route";
  129. } elsif ( $self->{stage} == CALCULATE_ROUTE ) {
  130. my $time = time;
  131. while ( !$self->{done} && (!$self->{maxTime} || !timeOut($time, $self->{maxTime})) ) {
  132. $self->searchStep();
  133. }
  134. if ($self->{found}) {
  135. delete $self->{openlist};
  136. delete $self->{solution};
  137. delete $self->{closelist};
  138. delete $self->{dest}{field};
  139. $self->setDone();
  140. debug "Map Solution Ready for traversal.n", "route";
  141. } elsif ($self->{done}) {
  142. my $destpos = "$self->{dest}{pos}{x},$self->{dest}{pos}{y}";
  143. $destpos = "($destpos)" if ($destpos ne "");
  144. $self->setError(CANNOT_CALCULATE_ROUTE, TF("Cannot calculate a route from %s (%d,%d) to %s %s",
  145. $field->name(), $self->{source}{x}, $self->{source}{y},
  146. $self->{dest}{map}, $destpos));
  147. debug "CalcMapRoute failed.n", "route";
  148. }
  149. }
  150. }
  151. ##
  152. # Array<Hash>* $Task_CalcMapRoute->getRoute()
  153. # Requires: $self->getStatus() == Task::DONE && !defined($self->getError())
  154. #
  155. # Return the calculated route.
  156. sub getRoute {
  157. return $_[0]->{mapSolution};
  158. }
  159. ##
  160. # String $Task_CalcMapRoute->getRoute()
  161. # Requires: $self->getStatus() == Task::DONE && !defined($self->getError())
  162. #
  163. # Return a string which describes the calculated route. This string has
  164. # the following form: "payon -> pay_arche -> pay_dun00 -> pay_dun01"
  165. sub getRouteString {
  166. my ($self) = @_;
  167. my @maps;
  168. foreach my $node (@{$self->{mapSolution}}) {
  169. push @maps, $node->{map};
  170. }
  171. push @maps, "$self->{dest}{map}";
  172. return join(' -> ', @maps);
  173. }
  174. sub searchStep {
  175. my ($self) = @_;
  176. my $openlist = $self->{openlist};
  177. my $closelist = $self->{closelist};
  178. unless ($openlist && %{$openlist}) {
  179. $self->{done} = 1;
  180. $self->{found} = '';
  181. return 0;
  182. }
  183. my $parent = (sort {$openlist->{$a}{walk} <=> $openlist->{$b}{walk}} keys %{$openlist})[0];
  184. debug "$parent, $openlist->{$parent}{walk}n", "route/path";
  185. # Uncomment this if you want minimum MAP count. Otherwise use the above for minimum step count
  186. #foreach my $parent (keys %{$openlist})
  187. {
  188. my ($portal, $dest) = split /=/, $parent;
  189. if ($self->{budget} ne '' && $openlist->{$parent}{zenny} > $self->{budget}) {
  190. # This link is too expensive
  191. delete $openlist->{$parent};
  192. next;
  193. } else {
  194. # MOVE this entry into the CLOSELIST
  195. $closelist->{$parent}{walk}   = $openlist->{$parent}{walk};
  196. $closelist->{$parent}{zenny}  = $openlist->{$parent}{zenny};
  197. $closelist->{$parent}{parent} = $openlist->{$parent}{parent};
  198. # Then delete in from OPENLIST
  199. delete $openlist->{$parent};
  200. }
  201. if ($portals_lut{$portal}{dest}{$dest}{map} eq $self->{dest}{map}) {
  202. if ($self->{dest}{pos}{x} eq '' && $self->{dest}{pos}{y} eq '') {
  203. $self->{found} = $parent;
  204. $self->{done} = 1;
  205. $self->{mapSolution} = [];
  206. my $this = $self->{found};
  207. while ($this) {
  208. my %arg;
  209. $arg{portal} = $this;
  210. my ($from, $to) = split /=/, $this;
  211. ($arg{map}, $arg{pos}{x}, $arg{pos}{y}) = split / /, $from;
  212. ($arg{dest_map}, $arg{dest_pos}{x}, $arg{dest_pos}{y}) = split(' ', $to);
  213. $arg{walk} = $closelist->{$this}{walk};
  214. $arg{zenny} = $closelist->{$this}{zenny};
  215. $arg{steps} = $portals_lut{$from}{dest}{$to}{steps};
  216. unshift @{$self->{mapSolution}}, %arg;
  217. $this = $closelist->{$this}{parent};
  218. }
  219. return;
  220. } elsif ( Task::Route->getRoute($self->{solution}, $self->{dest}{field}, $portals_lut{$portal}{dest}{$dest}, $self->{dest}{pos}) ) {
  221. my $walk = "$self->{dest}{map} $self->{dest}{pos}{x} $self->{dest}{pos}{y}=$self->{dest}{map} $self->{dest}{pos}{x} $self->{dest}{pos}{y}";
  222. $closelist->{$walk}{walk} = scalar @{$self->{solution}} + $closelist->{$parent}{$dest}{walk};
  223. $closelist->{$walk}{parent} = $parent;
  224. $closelist->{$walk}{zenny} = $closelist->{$parent}{zenny};
  225. $self->{found} = $walk;
  226. $self->{done} = 1;
  227. $self->{mapSolution} = [];
  228. my $this = $self->{found};
  229. while ($this) {
  230. my %arg;
  231. $arg{portal} = $this;
  232. my ($from, $to) = split /=/, $this;
  233. ($arg{map}, $arg{pos}{x}, $arg{pos}{y}) = split / /, $from;
  234. $arg{walk} = $closelist->{$this}{walk};
  235. $arg{zenny} = $closelist->{$this}{zenny};
  236. $arg{steps} = $portals_lut{$from}{dest}{$to}{steps};
  237. unshift @{$self->{mapSolution}}, %arg;
  238. $this = $closelist->{$this}{parent};
  239. }
  240. return;
  241. }
  242. }
  243. # Get all children of each openlist.
  244. foreach my $child (keys %{$portals_los{$dest}}) {
  245. next unless $portals_los{$dest}{$child};
  246. foreach my $subchild (keys %{$portals_lut{$child}{dest}}) {
  247. my $destID = $subchild;
  248. my $mapName = $portals_lut{$child}{source}{map};
  249. #############################################################
  250. my $penalty = int($routeWeights{lc($mapName)}) +
  251. int(($portals_lut{$child}{dest}{$subchild}{steps} ne '') ? $routeWeights{NPC} : $routeWeights{PORTAL});
  252. my $thisWalk = $penalty + $closelist->{$parent}{walk} + $portals_los{$dest}{$child};
  253. if (!exists $closelist->{"$child=$subchild"}) {
  254. if ( !exists $openlist->{"$child=$subchild"} || $openlist->{"$child=$subchild"}{walk} > $thisWalk ) {
  255. $openlist->{"$child=$subchild"}{parent} = $parent;
  256. $openlist->{"$child=$subchild"}{walk} = $thisWalk;
  257. $openlist->{"$child=$subchild"}{zenny} = $closelist->{$parent}{zenny} + $portals_lut{$child}{dest}{$subchild}{cost};
  258. }
  259. }
  260. }
  261. }
  262. }
  263. }
  264. 1;