Jump to content
  • Advertisement
Sign in to follow this  
xucaen

A* algorithm on a top down vertical scrolling shooter?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!