Public Group

# A* algorithm on a top down vertical scrolling shooter?

This topic is 1351 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Is it even possible? If the world is scrolling downwards, and the player is constantly moving upwards, how would the A* algorithm work?

##### Share on other sites
Even if the world is scrolling, the data structure representing the level data does not need to. So yeah, I don't see any problems. Edited by Nypyren

##### Share on other sites

The screen is not moving continuously, but in increments. A* would work. Not sure why you would want A* search in a vertical shooter though.

This did make me wonder about the (extremely loosely) related theoretical question: Is A* search still best for n dimensional searches, or are other searches better in other cases?

##### Share on other sites

I agree with Nypyren, the world itself isn't changing, just what's in view.  That said, unless you're vertical shooter has a lot of terrain to pathfind around, basic steering is probably better.

EDIT: To expand on my first sentence, think of an RTS like starcraft, does the pathfinding change just because the user is scrolling the viewport?  No, pathfinding is essentially unchanged.

Edited by ferrous

##### Share on other sites

It might be the case that the world is procedurally generated on demand.

In order to use A* you need to have a starting position and a goal position, and A* will give you the path from start -> finish. So if you have those bits of information and simply want to run the A* algorithm every time the exposed part of the world changes, which might be every frame, then that's do-able in general.

However, if as-it sounds your player is constrained such that they can only move horizontally, whilst the world moves vertically, then you have a bit of a snag because you are limited to moving in the following effective directions: up, diagonally up & left, and diagonally up & right. If the resulting path from A* contains portions which require travelling in other directions, then your player will be unable to follow the path.

It's at this point that I feel you will need to provide a more detailed description of the problem before we can give the right bit of advice. It might be that what you want is something very different, more along the lines of the minimax algorithm, whereby at any point in time you just want to work out which direction (left, right, or neither) is the most ... erm *productive*.

##### Share on other sites

However, if as-it sounds your player is constrained such that they can only move horizontally, whilst the world moves vertically, then you have a bit of a snag because you are limited to moving in the following effective directions: up, diagonally up & left, and diagonally up & right. If the resulting path from A* contains portions which require travelling in other directions, then your player will be unable to follow the path.

Those are interesting changes to the algorithm, but shouldn't be too hard to make. If the directions you can move are limited, just don't search the invalid directions when determining the possible path. If everything is constantly moving forward, so relative to the map you can move up faster than you can move down, give upward movement a different cost than downward movement.

##### Share on other sites

A* will continue to do exactly what it does.  In the land of computer theory, A* is a shortest path graph traversal algorithm. It works with any problem that can be converted/reduced into a theoretical graph of with vertices and edges. Dijkstra's algorithm (another shortest path algorithm) can be implemented as a special case, and other shortest path algorithms may also be good solutions in different scenarios.

For the problem described there may be many other algorithms.

Based on the description, I can imagine most of the gradient descent algorithms could be a good fit. They typically require much less space and processing to compute.

##### Share on other sites

Just look to the bullets, if they move normal, the background is moving only.

I personally let the background move only.

1. 1
2. 2
Rutin
19
3. 3
khawk
19
4. 4
5. 5
A4L
11

• 9
• 12
• 16
• 26
• 10
• ### Forum Statistics

• Total Topics
633771
• Total Posts
3013761
×