Messages

16

Programming / Re: Spell casting types of costs

« on: December 18, 2011, 11:58:45 PM »

Wizard101 isn't a very good game, but I like the battle mechanism a lot and I feel it would do great in roguelike settings.

The player owns a deck of cards (spells/skills). Game would goes somewhat like this:

• When entering a new level, the player a) shuflles his discard, deck and hand b) draw a new hand
• The player can, anytime, play a card from his hand if he has one
• When used the card is discarded and another is drawn (if any left)
• Class/skills/whatever unlock access to some cards and make them more powerful
• Some piece of equipement (weapons mostly) can provide "perma" cards that aren't discarded (but use one hand slot for a relatively weak effect)

That last point is quite different from the original but I like it better.

Anyway, I consider using a similar system for my project, but since I never finish anything if anyone like the idea it's not mine anyway

17

Programming / Re: Question about pathfinding in a particular context

« on: December 18, 2011, 01:28:01 AM »

The code pasted earlier has a bug, only checks for diagonal moves. "(dx != 0 && dy != 0)" should be "(dx != 0 || dy != 0)". It's fine other than that and It's way faster than I thought it would be, in 1000ms over 1500 iterations of randomly filling a 40x40 map with walls, basic and one-way tiles, picking 5 random sources, 5 random targets and computing. Now to add LOS.

Thank you Z, helped a ton. I think I'll stick around quite a bit

ps: Hydra Slayer is a pretty cool game Do you get to wield more than 2 weapons at some point?

EDIT:

Okay. A fun issue I had I'd like to relate here.

I had another bug with my code, not directly with the code posted earlier but with my Vector class.

To know when to stop computing I check if a set of targets is empty or not. Targets are x, y coordinates stored via a Vector class. The set is a HashSet<Vector>. But the remove operation didn't work and the algorithm computed all the map.

The reason wasn't that hard to find: my Vector class did override the "equals" method but not the "hashCode" one.

Lost no time and added a StringBuffer based one:

Code: [Select]

public int hashCode() {
StringBuffer result = new StringBuffer(x);
result.append(" "); // so 11, 1 and 1, 11 don't have same hash
result.append(y);
return result.toString().hashCode();
}
Worked as intented but the algorithm got 30% slower (a bit more than 1000 iterations per 1000 ms). Meaning that I'd have better performances WITHOUT a set of targets and by letting the algorithm compute the all map.

I then tried another hash:

Code: [Select]

public int hashCode() {
return x + y * 10000; // correct as long the width is <= 10000
}
Still worked as intented but was now 30% faster than the bugged version and twice faster than the previous working version (a bit more than 2100 iterations per 1000 ms). Felt good!

But out of curiosity I removed the target based test all together and let the algorithm compute the all map. It got only 5% slower (if not less) than the last version (a bit more than 2000 iterations per 1000 ms).

I guess it illustrates quite well what people keep telling me: don't bother with optimisations yet. I removed all target related stuff as it is as fast and easier to use.

18

Programming / Re: Question about pathfinding in a particular context

« on: December 17, 2011, 10:19:29 PM »

About BFS it's pretty much what I had in mind when I mentioned Dijkstra as I didn't plan on taking time required to travel into account. When looking it up on wikipedia the only difference I saw from my way to do things was the stop condition. My fault for being ignorant!

About passability of blocked tiles, I plan on leaving them passable as far as pathfinding goes. If best option is blocked, I'll have them take the second one so they don't wait in queue if the path is several tiles wide (which will be the case more often than not).

The other option to treat them as passable in a given number of turn sounds good too. But wouldn't that mean to use a "true" Dijkstra instead of a "simple" BFS?

I just finished a BFS implementation that uses a set of sources, a set of targets and supports one way tiles. Will test it a bit to see how it goes but here is the relevant (java) code just for the heck of showing something: http://pastebin.com/T63196Et

ps: I'll try Hydra Slayer right now. Already had a look to Hyperbolic Rogue and found it quite interesting.

19

Programming / Re: Question about pathfinding in a particular context

« on: December 17, 2011, 05:59:03 PM »

if they target the nearest, just start Dijkstra with all the targets as sources

Genious. Several source, why didn't I think of that? That solves the summon issue and opens my mind to a lot of possibilities, thank you.

BTW since you seem to assume that each tile can be walked in time 1 (even the shallow water) BFS should work, and it is simpler to implement and faster than the general Dijkstra algorithm.

From what I understand, BFS is like a regular Dijkstra that stops once the "target" is found. However I have multiple targets (trackers). I can stop once all the targets are reached. Problem, what if the best path for a given mobile is blocked by another one? My current idea was to take the second best option but there might not be one computed yet. Or I can take neighbours tiles as targets as well, guess it would work and be indeed faster.

Both points are similar, multiple source and multiple targets. Also gives me ideas on how to implement this still foggy idea with pre-computed pathings from an area to another.

I think your method might not be clear to some people (you are either running A* for each monster, or Dijkstra once per each class of monsters which have the same goal and mobility).

Indeed wasn't very clear, but you got it right.

Thank you Z!

20

Programming / Question about pathfinding in a particular context

« on: December 17, 2011, 03:48:04 PM »

Hi! English isn't my native language so I hope this won't be too hard of a read.

I'm working on a roguelike project, written using Java, as a learning experience. Right now I'm trying to decide on a pathfinding algorithm that would fit my settings.

Here are (I think) all the relevant aspects:

• A level is made of (at most) 40x40 tiles.
• There is no fog of war.
• Some maps layout might be maze-like.
• Monsters spawn continuously.
• Can have up to about 100 monsters at the same time.
• Most monsters will track the player no matter how far they are.
• The player has access to summoning abilities.

Also relevant are the possible tile types:

• Basic. No restrictions.
• Wall. Blocks all movement.
• Shallow water. Shouldn't matter for pathfinding. Even if it slows some mobiles the shortest path is decided on the number of moves.
• Deep Water. Need to be flying or able to swim to get through.
• Lava. Need to be flying or fire immune to get through.
• One way. Basic tile that forbid movements from a given direction. Need to be flying to get through from the wrong side.

IMO why choose Djikstra over A*:

• Relatively small maps.
• Lots of simulatenously tracking monsters.
• Maze-Like maps.

IMO why choose A* over Djikstra:

• Summons (some mobiles can track something else than the player).
• Variety of tiles with different restrictions on movement depending on who's tracking.

Another option: A* with "helpers". I'm not sure how to do that, but those pathfinding "helpers" would be computed during map loading/generation. First by identifying "areas" and then how to get from one to another. An area is a subpart of the map where A* works great (no need to move backward). Sounds complex but if I can pull it off it should be efficient. A bit worried tho on how the movements will look when, say, the player and the monster tracking him are close but in different areas.

My plan at the moment is to go with Djikstra for monsters, some kind of A* for summons, and see how it goes. However pretty sure it will be slow as I'll have to run the algorithm several times each time the player moves (because of tile types). Thoughts?