next »

[Glaiel-Gamer]

http://spamtheweb.com/ul/upload/150209/47681_MPTD.php

I'm so happy I got this to work.

The enemies will avoid the walls that are close together, unless it's significantly shorter to go that route or if its the only route to go. Otherwise they spread out and avoid the walls, centering themselves between passages and not hugging walls.

All this runs with as many enemies as I want, with as many walls as I want, at the cost of a little computation every time a wall is placed.

Oh ya and in the demo click to place a red and blue "tower" then click and drag to place some walls. The color channels are green: distance to any wall. Blue: distance to blue tower. Red: distance to red tower. They make pretty patterns :p. Then click space and you can drop enemies (lots of enemies)



</happy>

[Glaiel-Gamer]

also anyone have a good link regarding making a priority queue in flash? I was just sorting an array and I know that's slower than it needs to be.

[John Nesky]

http://code.google.com/p/as3ds/source/browse/trunk/src/de/polygonal/ds/PriorityQueue.as

[increpare]

nice, dude

[Glaiel-Gamer]

http://code.google.com/p/as3ds/source/browse/trunk/src/de/polygonal/ds/PriorityQueue.as

thanks! I modified it a little to fit my needs, works pretty well.

[nihilocrat]

Awesome job, definitely more than my slack ass could do before getting frustrated and moving on.

[shrimp]

Nice! The patterns are indeed pretty and the movement flows nicely.

Is it a vector field? What do the tile colours mean?

[raigan]

Is it a vector field? What do the tile colours mean?

I think it's 3 separate scalar fields:

The color channels are green: distance to any wall. Blue: distance to blue tower. Red: distance to red tower.

But the beauty of distance maps is that you can generate vectors from them using the gradient http://en.wikipedia.org/wiki/Gradient. It's like magic!!

[Robotacon]

I have never thought about path finding it that way.
You're kind of using gravity! Brilliant! 

[shrimp]

The color channels are green: distance to any wall. Blue: distance to blue tower. Red: distance to red tower.

Gah... distracted by the pictures! OK, I see what's going on now. This is (coincidentally maybe?) very like the "motor schema" system of navigation. It's really hard to find any decent links... but then you've already implemented it so you don't need em anyway 

[5parrowhawk]

This is incredibly clever stuff. Bravo!

Can't help but notice, though, that it won't work for moving targets. Unless you have x waypoints on the level, each with its own distance map, and then pick the nearest waypoint within LOS of the moving target and make the enemies walk to that waypoint first.

Hmm... anyone else got ideas for making this work with a moving target?

[Loren Schmidt]

Wow, this is a really neat idea! I like being able to see the gradients in the demo.

The motion of the little characters is pretty compelling.

[moi]

That sounds very smart

[raigan]

Hmm... anyone else got ideas for making this work with a moving target?

Couldn't you just recalculate the distance map on-the-fly?

Actually, if red/blue is just distance-to-target, then you don't really need the red/blue channels since they're just going to be radial gradients -- rather than reconstructing the distance to the target from the grid you could just calculate the actual vector to the target. Assuming there are fewer entities than grid cells, this should be cheaper than updating the distance map. Unless of course you bake the gradient in an array and compose the updated distance map by "blitting" the radial gradient at the current target position, and/or you only update the distance map every N frames instead of every frame..


Supporting moving obstacles (green channel, which is the interesting/complicated part) would require updating the distance field. But again, you could instead use a direct/analytical method instead of the distance field -- find the vectors from your current position to any nearby obstacles and you've essentially got the corresponding distance value which would be baked in the map. Either way your entities are using steering behaviours, it's just a matter of whether they're looking up the inputs based on their current cell (or their current position in their current cell to be more accurate) or calculating them based on their current position. I think..

Distance maps let you share all those "vector to nearby obstacle" calculations -- you do the math once per grid cell and cache the results in the cell, and many entities can lookup the results in the cell rather than recalculate it all. Of course this might not be a win if you have few enemies, but the other nice thing about distance maps is that you can bake in complicated shapes like ellipses or other potential fields which might be awkward to represent directly. Plus they look totally awesome!

[bateleur]

This app is nice! 

Actually, if red/blue is just distance-to-target, then you don't really need the red/blue channels since they're just going to be radial gradients

Unless I'm misunderstanding something, they're distance-as-walked, not the cartesian distance. Calculating them requires walking the maze.

Supporting moving obstacles (green channel, which is the interesting/complicated part) would require updating the distance field.

The green channel will be much easier to update than the others in a typical case.

[Glaiel-Gamer]

Hmm... anyone else got ideas for making this work with a moving target?

You'd just recalculate it every frame. Each channel takes roughly the same time to calculate, and it does it pretty real-time. The advantage of this is that once you do it once then you can support as many enemies as the game can render.

Enemy code:

Code:

public function update(g:Grid):Boolean{
			var dir:int = 0;
			var val:int = g.getDist(x, y, targ, true);
			if(Math.random()<.2 || val > 9999){
				speed.x = 0;
				speed.y = 0;
				if(g.getDist(x-15, y, targ, true) < val) speed.x -= 2;
				if(g.getDist(x+15, y, targ, true) < val) speed.x += 2;
				if(g.getDist(x, y-15, targ, true) < val) speed.y -= 2;
				if(g.getDist(x, y+15, targ, true) < val) speed.y += 2;
				speed.x += (Math.random()-.5)
				speed.y += (Math.random()-.5)
				speed.norm();
				speed.scale(2);
			}
			sss.x += speed.x/8
			sss.y += speed.y/8
			if(sss.length > 2) sss.length = 2;
			if(g.getDist(x+sss.x, y, targ, true) < 9999) x += sss.x;
			if(g.getDist(x, y+sss.y, targ, true) < 9999) y += sss.y;
			
			if(val == 0)
				 return false;
			else return true;
		}

it's a pretty simple code really.

oh ya and speed really = acceleration and sss = speed, I was changing things around to get smooth motion and I forgot to go change the names.

[increpare]

oh ya and speed really = acceleration and sss = speed,

speed? looks like velocity to me 

anyway, that looks like a pretty interesting way of approaching things.

[raigan]

Unless I'm misunderstanding something, they're distance-as-walked, not the cartesian distance. Calculating them requires walking the maze.

Aha, that makes more sense..

[BorisTheBrave]

Unless I'm misunderstanding something, they're distance-as-walked, not the cartesian distance. Calculating them requires walking the maze.

Assuming Glaiel-Gamer is following the paper he linked in the other thread, it's neither. It's actually a diffusion forumula, which converges to distances as walked the more you run it. It significantly faster than distance finding when you are changing the scenery a lot (or also the target, providing the target moves in a continuous fashion). It's actually a pity it's just being used for tower defence (again, I'm assuming), it could probably handle moving worlds pretty well too, while old fashioned distance finding on a grid already works ok when you are only plonking down new towers occasionally.

[Glaiel-Gamer]

Assuming Glaiel-Gamer is following the paper he linked in the other thread, it's neither. It's actually a diffusion forumula, which converges to distances as walked the more you run it. It significantly faster than distance finding when you are changing the scenery a lot (or also the target, providing the target moves in a continuous fashion).

Actually, no, I was walking through the grid. I read up on that diffusion paper and am still trying to wrap my head around some of the concepts, and I don't like to blindly implement an algorithm that I don't fully understand. Maybe for the future.

On a related note however, I'm going to try using the number of units on each square as a weight for the pathfinding (in addition to the inverse wall distance as a weight), see how it looks. Might encourage enemies to spread out more without having to resort as much on the small random variation I have, along with taking alternate paths.

It's actually a pity it's just being used for tower defence (again, I'm assuming), it could probably handle moving worlds pretty well too, while old fashioned distance finding on a grid already works ok when you are only plonking down new towers occasionally.

Well it's not just any tower defense. I'm pissed at the lack of creativity (and lack of online multiplayer) in the tower defense genre, so I feel like ripping a hole through the genre.