Representing a complex environment in memory for use with a pathfinding algorithm

[adc]

I'm looking to write a pathfinding AI for a 2d platforming game - I've done some reading and I think I understand the general idea. I've also found some example code (in java, though my end result doesn't need to be in any particular language), so I'm going to work through that; I think, for the most part, I can get the algorithm itself going.

The issue I'm running into is how to represent the game (any game from the "fangame" genre, if that means anything to anyone) in memory to run the algorithm on. For the vast majority of movement, the game works on a pixel-based system (each frame = 3 pixels of horizontal movement, game is 800x600 typically). This introduces the concept of aligns; essentially, because you move 3 pixels horizontally at a time, it is impossible to reach 66% of the pixels at any time. However, it's possible to touch a wall to make yourself move only 1 or 2 pixels, changing which align you're currently on (and thus which pixels you can move to) and making certain jumps easier (or, in some cases, possible) to do. This concept also exists, albeit in a slightly altered fashion, for vertical alignment; the difference here is that the alignment is sub-pixel, never changing more than 1 pixel but affecting very precise jumps. This align changes when you jump, and differently when you jump in water. I'm going to be working on a formula that lets me accurately predict what my valign will be after a given jump, but for now I just want to get the basic movement working.

So, with that wall of text explanation out of the way, I'm not sure how to represent my environment in memory in such a way that I can add valign manipulation as a possible movement mechanic (though with a cost so high it'll only happen if the jump is not possible in any other way). I do have the luxury of knowing ahead of time what each screen is, but there are moving parts within the game (moving platforms and triggers which cause parts of the level to change).

An example of a screen in the game can be found here:



Spikes and apples kill you, metallic blocks are walkable, the weird almost-circle things are warps.

Let me know if I haven't explained anything clearly, or if extra info is needed. Thanks in advance!

[Ciccioo]

goddamit, i wanna be the guy gaiden, i raged hard on that

 

is the environment aligned to a grid? it looks like it is, this would make things pretty easy as you can just map exactly every item, and then consider your alignments only when you test for collisions

 

edit: moving parts and enemies aren't aligned to the grid for sure, but you could use a different storage for them. for instance you could have two mappings for each level:
the static objects map, which is a grid/matrix;
the moving objects map, which could be whatever you want, and since i wouldn't expect it to have too many items it could even be a simple list, which makes the update of the data structure trivial

[adc]

The only grid they could be "aligned" too is a pixel by pixel grid the same size as the game itself; blocks are 32x32, but there's no requirement for them to be locked to any grid. They can be placed on any pixel within the screen. I could do an 800x600 grid, but my concern is sub pixel alignments for jumps that require it. These wouldn't be accounted for on the 800x600 grid, and I have no idea how to deal with them outside of just doing an 800x60000 grid, which is obviously not ideal.

 

Also, not quite gaiden - significantly harder (no Western player has beaten it, and no Eastern player has provided proof) - but the same style of game .

[Guest]

I think it is potentially a mistake to couple your display coordinates to the game coordinates. You should represent positions internally in the game engine however best fits the algorithms and data structures involved, then use the display layer to convert the internal representation into the visual medium. Do you think sub-block movements are represented as "pixels" in minecraft? Me neither.

[adc]

The game engine is already written (though not by me, I do have the code), and unless I grossly misunderstand it that's how it works; holding left for one frame moves you 3 pixels to the left on the screen. I'm attempting to write a pathfinding AI to solve user created levels in this engine.

[Ciccioo]

The only grid they could be "aligned" too is a pixel by pixel grid the same size as the game itself; blocks are 32x32, but there's no requirement for them to be locked to any grid. They can be placed on any pixel within the screen. I could do an 800x600 grid, but my concern is sub pixel alignments for jumps that require it. These wouldn't be accounted for on the 800x600 grid, and I have no idea how to deal with them outside of just doing an 800x60000 grid, which is obviously not ideal.

 

Also, not quite gaiden - significantly harder (no Western player has beaten it, and no Eastern player has provided proof) - but the same style of game .

does this mean that the environment also has sub-pixel alignment? can a spike be placed at (40, 33.4)?

if a grid is not an option then you need to find some plane indexing data structure, like an Rtree

[adc]

does this mean that the environment also has sub-pixel alignment? can a spike be placed at (40, 33.4)?

if a grid is not an option then you need to find some plane indexing data structure, like an Rtree

As far as I can tell I am not able to place obstacles with sub pixel alignments. I guess I could do a simple pixel based grid, then, but I'm not sure how I would factor in vertical aligns for jumps given that grid.

[Ciccioo]

As far as I can tell I am not able to place obstacles with sub pixel alignments. I guess I could do a simple pixel based grid, then, but I'm not sure how I would factor in vertical aligns for jumps given that grid.

the character doesn't need to be placed in the grid, you can store his position in a different and more precise coordinate system. when you test for collisions, you have to approximate the subpixel position of the guy to the pixel position on the grid, and on that approximated position you check whether it hits something or it doesn't

[LePawel]

First of all: you could try representing the world and character in shapes and do some pixel-independent collision checking that way, which would eliminate precision problems. I've never used any 2D collision detection libraries though, so no idea how to even start, and it seems like modifying a lot of code to add that data in.

IMO you can use the 800x600 array, and since you have 3 types of pixel: air, good and bad so you need enums or shorts to represent it. All moving platforms can use their coordinates and size to submit changes in the grid as they move at pixel precision and all triggers follow suit (they remove block X, and use that block to add to changes array upon disappearing based in its position). No problems here.

This way you get a dynamic collision data, and you can extract only nearby pixels to do collision calculations or path predictions.

For the sub-pixel problem, here's how I see it:

Unless you store data about spikes and platforms with same precision as the character, there's no reason to be worried, and here's why:

Considering Green is the character and Red is the spike, as long as the character enters spike's pixel by any margin, it counts as touched, because whole pixel is considered a spike.

So you can always "round up" pixels in which character resides. Here's how the character pixel approximation would look like (you can see the original line).

Remember that you can only compare similar data within the lowest precision provided, so it's either mathematical shapes which have scalable precision or pixels, which have, well, pixel precision. Note that you can consider being fair, and round to nearest pixel rather than up, but I've no clue how to calculate that, it might be that the 2D engine itself will only partially increase alpha values for the parts of character that are between pixels, so you can check for alpha > 0 or alpha > 0.5 depending on your taste.

 

Hope it helped.