Formula for randomized dropping?

01/09/2011 18:44 Lateralus#1

I need a formula for random coordinate dropping (players/monsters, items/gold) around a variable radius. The number of coordinates shouldn't be greater than 33 (4*8+1).

I've had many ideas, and the best I could come up with is creating an array of length radius*8+1, initializing the values in the array to the corresponding array index, and shuffling the values in the array using the Fisher-Yates shuffle algorithm (O(nlogn)). This is extremely time consuming as far as writing the code since I have to test each value in the array for equality 33 times and increment/decrement the testing x and y coordinates for each test.

Is this the most efficient way of doing this? If not, is there an algorithm for a array with a maximum of 33 values that sorts in faster time than Fisher-Yates?

01/09/2011 20:43 pro4never#2

I think I'm completely missing the point here but are you not just wanting to pull random coords near a certain location?... Why would you go through all that trouble of generating all possible coords, shuffling them and then pulling one?

Just do a rand.next using bound X/Y and how far you want the spread.

Sorry if I'm missing the point of doing a more complex version but it does sound to me like you want to just pull a random coord nearby.

I've done a few versions of this... one being pull random coord and then check if it is free but you could just as easily do a for X for Y loop, check if it's free/valid and then return a list of valid coords...

01/09/2011 23:50 Lateralus#3

Quote:

Originally Posted by pro4never

I think I'm completely missing the point here but are you not just wanting to pull random coords near a certain location?... Why would you go through all that trouble of generating all possible coords, shuffling them and then pulling one?

Just do a rand.next using bound X/Y and how far you want the spread.

Sorry if I'm missing the point of doing a more complex version but it does sound to me like you want to just pull a random coord nearby.

I've done a few versions of this... one being pull random coord and then check if it is free but you could just as easily do a for X for Y loop, check if it's free/valid and then return a list of valid coords...

That's what I want to do, but, and correct me if I'm wrong, doing a for X for Y loop, wouldn't exactly randomize the item/gold dropping, and pulling a random coordinate can be inefficient if there are few available spaces on the ground for the item/gold to drop onto.

Actually, do you know which method the official servers use? I assumed that it was randomized, but I'm not 100%.

01/10/2011 00:49 pro4never#4

I'm not sure what method the tq servers use but as for the 'most efficient' way of doing this... probably interfaces + some sort of data structuring the ground items.

The for x/y loop would obviously still need to be randomized (you'd receive a list of valid coords for dropping and then just randomize those which it seems is what you are already doing... but if you wanted to 'cheat' a bit you could store them as an array and just pull a random element 0-elementcount to avoid having some intensive randomization process (we're talking item drop locations here... it's not gotta be absolutely perfectly random lol!)

Personally I like the idea of doing that as it deals with crowded map floors easily.

My map system right now holds a dictionary of ground items using the structure <Coord, list<object>>. That way I ONLY pull coords that have elements on them (mob, player, items, etc) and can write simple methods to pull a list of items on screen or you could reverse that and find empty/non item'd coords.

01/10/2011 05:44 ChingChong23#5

this what your after?

Code:

public static Point validDropTile(int x, int y, int map) {
	int[][] dirs = {{x, y}, {x - 1, y}, {x, y - 1}, {x - 1, y - 1}, {x + 1, y + 1}, {x, y + 1}, {x + 1, y}, {x + 1, y - 1}, {x - 1, y + 1}};
	for(int i=0; i < dirs.length; i++) {
	    if(!isTileBlocked(map, dirs[i][0], dirs[i][1]) && !tileHasItem(dirs[i][0], dirs[i][1], map))
		return new Point(dirs[i][0], dirs[i][1]);
	}
	return null;
    }

    public static boolean tileHasItem(int x, int y, int map) {
	for(GroundItem i : World.getWorld().getMaps().get(map).getGroundItems()) {
	    if(i.getX() == x && i.getY() == y)
		return true;
	}
	return false;
    }

Code:

    if (player.getCharacter().getInventory().hasItem(uid)) {
		Item i = player.getCharacter().getInventory().getItem(uid);
		Point valid = Formula.validDropTile(player.getCharacter().getX(), player.getCharacter().getY(), player.getCharacter().getMapid());
		if (valid == null) {
		    return;
		}
		int map = player.getCharacter().getMapid();
		final GroundItem gi = new GroundItem(i.getUID(), i.getID(), i.getPlus(), i.getBless(), i.getEnchant(), i.getSoc1(), i.getSoc2(), (int) valid.getX(), (int) valid.getY(), map);
		player.getMap().addGroundItem(gi, valid, map);
		player.getCharacter().getInventory().removeItem(i);
		player.getActionSender().removeItem(i);
		World.getWorld().getTimerService().add(new Timer(90000, null) {

		    public void execute() {
			if (gi != null) {
			    World.getWorld().getMaps().get(gi.getMap()).getGroundItems().remove(gi);
			    for (Player p : World.getWorld().getMaps().get(gi.getMap()).getPlayers().values()) {
				if (Formula.inView(gi.getX(), gi.getY(), p.getCharacter().getX(), p.getCharacter().getY())) {
				    p.getCharacter().getItemsInView().remove(gi);
				    p.getActionSender().removeGroundItem(gi);

				}
			    }
			}
		    }
		});

	    }

01/11/2011 03:41 Lateralus#6

Thank both of you very much, got it working! :D