From: Kimmo R. <ki...@us...> - 2009-03-17 19:20:57
|
Update of /cvsroot/arianne/stendhal/src/games/stendhal/server/core/rp In directory 23jxhf1.ch3.sourceforge.com:/tmp/cvs-serv30247/src/games/stendhal/server/core/rp Modified Files: StendhalRPAction.java Log Message: a smarter placeat() algorithm. places entities at minimum euclidean distance within minimum walking distance. fixes bug [1681767] "Doors shift you aside" Index: StendhalRPAction.java =================================================================== RCS file: /cvsroot/arianne/stendhal/src/games/stendhal/server/core/rp/StendhalRPAction.java,v retrieving revision 1.28 retrieving revision 1.29 diff -C2 -d -r1.28 -r1.29 *** StendhalRPAction.java 15 Mar 2009 18:15:12 -0000 1.28 --- StendhalRPAction.java 17 Mar 2009 19:20:41 -0000 1.29 *************** *** 31,34 **** --- 31,35 ---- import games.stendhal.server.entity.player.Player; + import java.awt.Point; import java.awt.Rectangle; import java.awt.Shape; *************** *** 89,93 **** + " is in a protection zone"); ! String name = getNiceVictimName(victim); player.sendPrivateText("The powerful protective aura in this place prevents you from attacking " --- 90,94 ---- + " is in a protection zone"); ! final String name = getNiceVictimName(victim); player.sendPrivateText("The powerful protective aura in this place prevents you from attacking " *************** *** 106,110 **** } else { // Only allow owners, if there is one, to attack the pet ! Player owner = ((DomesticAnimal) victim).getOwner(); if ((owner != null) && (owner != player)) { player.sendPrivateText("You pity " + getNiceVictimName(victim) + " too much to kill it."); --- 107,111 ---- } else { // Only allow owners, if there is one, to attack the pet ! final Player owner = ((DomesticAnimal) victim).getOwner(); if ((owner != null) && (owner != player)) { player.sendPrivateText("You pity " + getNiceVictimName(victim) + " too much to kill it."); *************** *** 349,352 **** --- 350,358 ---- } + + // the total area checked is 2n(n+1) + 1 ; choose n so that it's about + // the same as in the old algorithm 36 => 2665 squares vs the old 2601 + /** maximum walking distance from the center */ + private static final int maxDisplacement = 36; /** * Places an entity at a specified position in a specified zone. This will *************** *** 366,374 **** * @return true, if it was possible to place the entity, false otherwise */ ! public static boolean placeat(final StendhalRPZone zone, final Entity entity, final int x, ! final int y, final Shape allowedArea) { if (zone == null) { return false; } // check in case of players that that they are still in game // because the entity is added to the world again otherwise. --- 372,381 ---- * @return true, if it was possible to place the entity, false otherwise */ ! public static boolean placeat(final StendhalRPZone zone, final Entity entity, int x, ! int y, final Shape allowedArea) { if (zone == null) { return false; } + // check in case of players that that they are still in game // because the entity is added to the world again otherwise. *************** *** 379,465 **** } } ! ! // Look for new position ! int nx = x; ! int ny = y; ! if (zone.collides(entity, x, y)) { boolean checkPath = true; ! ! if (zone.collides(entity, x, y, false) ! && (entity instanceof Player)) { ! // something nasty happened. The player should be put on a spot ! // with a real collision (not caused by objects). // Try to put him anywhere possible without checking the path. checkPath = false; } ! ! boolean found = false; ! ! // We cannot place the entity on the orginal spot. Let's search ! // for a new destination up to maxDestination tiles in every way. ! final int maxDestination = 20; ! ! outerLoop: for (int k = 1; k <= maxDestination; k++) { ! for (int i = -k; i <= k; i++) { ! for (int j = -k; j <= k; j++) { ! if ((Math.abs(i) == k) || (Math.abs(j) == k)) { ! nx = x + i; ! ny = y + j; ! if (!zone.collides(entity, nx, ny)) { ! ! // OK, we may place the entity on this spot. ! ! // Check the possibleArea now. This is a ! // performance ! // optimization because the next step ! // (pathfinding) ! // is very expensive. (5 seconds for a ! // unplaceable ! // black dragon in deathmatch on 0_ados_wall_n) ! if ((allowedArea != null) ! && (!allowedArea.contains(nx, ny))) { ! continue; ! } ! ! // We verify that there is a walkable path ! // between the original ! // spot and the new destination. This is to ! // prevent players to ! // enter not allowed places by logging in on top ! // of other players. ! // Or monsters to spawn on the other side of a ! // wall. ! ! final List<Node> path = Path.searchPath(entity, zone, ! x, y, new Rectangle(nx, ny, 1, 1), ! maxDestination * maxDestination, false); ! if (!checkPath || !path.isEmpty()) { ! ! // We found a place! ! ! found = true; ! ! // break all for-loops ! break outerLoop; ! ! } ! } ! } ! } ! } ! } ! ! if (!found) { logger.info("Unable to place " + entity.getTitle() + " at " + zone.getName() + "[" + x + "," + y + "]"); return false; } } ! ! // ! // At this point the valid position [nx,ny] has been found ! // ! final StendhalRPZone oldZone = entity.getZone(); final boolean zoneChanged = (oldZone != zone); --- 386,411 ---- } } ! if (zone.collides(entity, x, y)) { boolean checkPath = true; ! if (zone.collides(entity, x, y, false) && (entity instanceof Player)) { ! // Trying to place a player on a spot with a real collision ! // (not caused by objects). Can happen with teleport. // Try to put him anywhere possible without checking the path. checkPath = false; } ! ! final Point newLocation = findLocation(zone, entity, allowedArea, x, y, checkPath); ! ! if (newLocation == null) { logger.info("Unable to place " + entity.getTitle() + " at " + zone.getName() + "[" + x + "," + y + "]"); return false; } + + x = newLocation.x; + y = newLocation.y; } ! final StendhalRPZone oldZone = entity.getZone(); final boolean zoneChanged = (oldZone != zone); *************** *** 516,520 **** * [Re]position (possibly while between zones) */ ! entity.setPosition(nx, ny); /* --- 462,466 ---- * [Re]position (possibly while between zones) */ ! entity.setPosition(x, y); /* *************** *** 535,539 **** */ if (sheep != null) { ! if (placeat(zone, sheep, nx, ny)) { player.setSheep(sheep); sheep.setOwner(player); --- 481,485 ---- */ if (sheep != null) { ! if (placeat(zone, sheep, x, y)) { player.setSheep(sheep); sheep.setOwner(player); *************** *** 545,549 **** if (pet != null) { ! if (placeat(zone, pet, nx, ny)) { player.setPet(pet); pet.setOwner(player); --- 491,495 ---- if (pet != null) { ! if (placeat(zone, pet, x, y)) { player.setPet(pet); pet.setOwner(player); *************** *** 574,581 **** if (logger.isDebugEnabled()) { logger.debug("Placed " + entity.getTitle() + " at " ! + zone.getName() + "[" + nx + "," + ny + "]"); } return true; } } --- 520,663 ---- if (logger.isDebugEnabled()) { logger.debug("Placed " + entity.getTitle() + " at " ! + zone.getName() + "[" + x + "," + y + "]"); } return true; } + + /** + * Find a new place for entity + * @param zone zone to place the entity in + * @param entity the entity to place + * @param allowedArea only search within this area for a possible new position, + * or null if the whole normal search area should be used + * @param x the x coordinate of the search center + * @param y the y coordinate of the search center + * @param checkPath if true, check that there's a valid path to the center + * + * @return location of the new placement, or null if no suitable place was found + */ + private static Point findLocation(final StendhalRPZone zone, final Entity entity, + final Shape allowedArea, final int x, final int y, final boolean checkPath) { + /* + * Minimum Euclidean distance within minimum walking distance + */ + for (int totalShift = 1; totalShift <= maxDisplacement; totalShift++) { + for (int tilt = (totalShift + 1)/ 2; tilt > 0; tilt--) { + final int spread = totalShift - tilt; + + int tmpx = x - tilt; + int tmpy = y - spread; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + tmpx = x + tilt; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + tmpy = y + spread; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + tmpx = x - tilt; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + + // center spots of the equidistance rectangle. + if (spread == tilt) { + continue; + } + + tmpx = x - spread; + tmpy = y - tilt; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + tmpx = x + spread; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + tmpy = y + tilt; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + tmpx = x - spread; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + } + + // Do tilt = 0 case here, since it takes only 4 checks + int tmpx = x; + int tmpy = y - totalShift; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + tmpy = y + totalShift; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + tmpy = y; + tmpx = x - totalShift; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + tmpx = x + totalShift; + if (isValidPlacement(zone, entity, allowedArea, x, y, tmpx, tmpy, checkPath)) { + return new Point(tmpx, tmpy); + } + } + + return null; + } + + /** + * Check if a new placement for an entity is valid + * + * @param zone the zone where the entity should be placed + * @param entity the entity to place + * @param allowedArea if specified, restrict placement within this area + * @param oldX the x coordinate from where the entity was displaced + * @param oldY the y coordinate from where the entity was displaced + * @param newX the x coordinate of the new placement + * @param newY the y coordinate of the new placement + * @param checkPath if true, check that there is a path from <code>(newX, newY)</code> + * to <code>(oldX, oldY)</code> + * + * @return true if placing is possible, false otherwise + */ + private static boolean isValidPlacement(final StendhalRPZone zone, final Entity entity, + final Shape allowedArea, final int oldX, final int oldY, + final int newX, final int newY, final boolean checkPath) { + if (!zone.collides(entity, newX, newY)) { + // Check the possibleArea now. This is a + // performance + // optimization because the pathfinding + // is very expensive. + if ((allowedArea != null) && (!allowedArea.contains(newX, newY))) { + return false; + } + if (!checkPath) { + return true; + } + + // We verify that there is a walkable path + // between the original + // spot and the new destination. This is to + // prevent players to + // enter not allowed places by logging in on top + // of other players. + // Or monsters to spawn on the other side of a + // wall. + final List<Node> path = Path.searchPath(entity, zone, + oldX, oldY, new Rectangle(newX, newY, 1, 1), + 400 /* maxDestination * maxDestination */, false); + if (!path.isEmpty()) { + // We found a place! + return true; + } + } + return false; + } } |